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:
Create two for loops.
Outer loop iterates through the characters in the first string in the array.
Inner loop iterates through the characters in all the others strings in the array.
In each iteration, we check if each character in the first string matches the corresponding characters in all the others strings in the array.
If they match, continue iterating.
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"].
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).
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".
As you can see the first letters of both strings match, so we increment j by 1. Now i=0 and j=2.
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".
We now move to the next iteration of the outer loop i=1 and j=1.
Again, the 2nd characters of first and second strings match, so increment j by 1. Now i=1 and j=2.
As you see from above diagram, the second letters of all strings in the array match, hence we add it to our result.
We perform similar steps in the third iteration of the outer loop i=2 and j=1.
Again as seen in above diagram 3rd characters of 1st and second strings match. So, we move to i=2 and j=2.
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.
