top of page
  • LinkedIn
  • Facebook
  • YouTube
  • Twitter
  • Instagram
  • Pinterest
  • Tumblr
  • Vkontakte

Longest Common Prefix - LeetCode Fast & Simple Solution

Hello coders! Today, let's solve yet another leetcode problem, Longest Common Prefix. This is an article in our series leetcode problem solutions, so make sure to check out other leetcode problem solutions in this series, after you finish this one 😉.


Problem Statement


Find the longest common prefix from the given array of strings. Return an empty string "", if no common prefix is found.


Example 1:

Input: strs = ["preview","prepare","prevent"]
Output: "pre"

Example 2:

Input: strs = ["pan","can","dog"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

  • 1 <= strs.length <= 200

  • 0 <= strs[i].length <= 200

  • strs[i] consists of only lowercase English letters.


Solution


This is marked as an easy problem on leetcode, and it is indeed an easy solution except for a couple of edge cases that we have to cover.


Here we are asked to find the longest common prefix from the given array of strings. A prefix is a continuous sequence of letters at the beginning of the string. For instance, for string "leetcode" these are the possible prefixes: "l" "le" "lee" "leet" "leetc" and so on. We need to find the common prefix that is longest among all the strings in the given string array. For example, if strs = ["can", "cant", "candy"], the longest common prefix here is "can". Similarly for strs = ["bad", "bat", "bank"], the longest common prefix is "ba".


This problem can be easily solved using a O(m*n) solution. In this solution, we compare each character in the first string with the corresponding characters in all the others strings in the given string array. If all corresponding characters match we continue checking. We stop checking and return the result as soon as a mismatch is found.


Algorithm


Here is how the algorithm works:

  1. Create two for loops.

  2. Outer loop iterates through the characters in the first string in the array.

  3. Inner loop iterates through the characters in all the others strings in the array.

  4. In each iteration, we check if each character in the first string matches the corresponding characters in all the others strings in the array.

    1. If they match, continue iterating.

    2. If there is a mismatch in any of the strings, stop the iteration and return the prefix up to which there was a match as the result.


Simulation


Lets understand this algorithm with an example. Consider strs=["flower", "flow", "flight"].


string array example

The expected result here is "fl" which is the longest common prefix among the three strings in the input array. Lets see how our algorithm works to arrive at the result.


The algorithm uses two for loops. Outer loop is used to keep track of the letter in the strings we compare. Inner loop keeps track of the strings in the array.


i is the outer loop index and it runs from 1st letter in the 1st string till the last letter (Index 0 to n-1. Where n is the length of the first string). j is the in inner loop index and it runs from 2nd string in the array till the last string (Index 1 to m-1. Where m is the length of the array).


strs array example

Initially we start i=0 and j=1, which means that we will be comparing the first letter in the first string i.e. "f" with the first letter in the 2nd string "f".


strs array example

As you can see the first letters of both strings match, so we increment j by 1. Now i=0 and j=2.


strs array example

Again the first letters in both these strings match. Now, we have reached the end of the array, and the first characters in all the strings match. Therefore, we can consider it for our result. So, our current result="f".


strs array example

We now move to the next iteration of the outer loop i=1 and j=1.


strs array example

Again, the 2nd characters of first and second strings match, so increment j by 1. Now i=1 and j=2.

strs array example

As you see from above diagram, the second letters of all strings in the array match, hence we add it to our result.

strs array example

We perform similar steps in the third iteration of the outer loop i=2 and j=1.

strs array example

Again as seen in above diagram 3rd characters of 1st and second strings match. So, we move to i=2 and j=2.

strs array example

Now if you observe, 3rd character of first string is "o", but the 3rd character of third string is "i". Clearly they do not match, which means that the 3rd character is not same in all strings in the given input array, hence it cannot be part of our result. At this point we need to stop the algorithm and return "fl" as the result.


One edge that we need to cover here for other examples is if i goes out of bounds in either strings that we are comparing. In such cases we need to stop the iteration and return the matched prefix so far as result. We can detect such cases using the condition i>=length(strs[j]) as shown in code below.


Want to master coding? Looking to learn new skills and crack interviews? We recommend you explore these tailor made courses:


Code


Go Solution


Python Solution

Java Solution

JavaScript Solution

C++ Solution

C# Solution

PHP Solution

Kotlin Solution

Swift Solution

Ruby Solution


Complexity Analysis


Time Complexity


In this algorithm, we iterate through the characters in the first string and compare it with the corresponding characters in the rest of the strings. So, if m is the length of the first string and n is the total number of strings in the array, in the worst case outer loop runs m times and inner loop runs (n-1) times. So the worst case time complexity of this solution is O(m*n).


Space Complexity


The space complexity is O(1) because the algorithm does not use any extra space.


That brings us to the end of this article. We sincerely appreciate the time you've taken to read through it. If there are any questions or doubts, don't hesitate to voice them in the comments section below. We're here to assist you and will be more than happy to provide answers.


If you found value in this article, we encourage you to subscribe to both our website and YouTube channel. Your support fuels our motivation to continue producing more insightful articles like this one in the future.


Don't forget to delve into more such fascinating articles from Code Recipe in our blogs section. There's a wealth of knowledge waiting for you there!


Code Recipe Limited Time Offer: Get 100% discount on Code Recipe Membership Plan. Join now and get exclusive access to premium content for free. Hurry! Offer only available for a limited time - Join now.




88 views1 comment

Recent Posts

See All

1 comentario


Code Recipe
Code Recipe
10 mar

Hello Coders!


Code Recipe is now on YouTube! For videos on latest topic visit our YouTube channel: Code Recipe 


Visit Now: https://www.youtube.com/@coderecipeofficial


Do not forget to subscribe to our channel if you find the videos useful. Your support means a lot to us!


Happy Learning. Ba bye! 😊

Code Recipe YouTube Channel

Me gusta

We are now on YouTube!

Prefer learning through videos? No worries! Visit Code Recipe on YouTube now.