Longest Common Prefix
Introduction
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string ""
Example 1
Output: "fl"
Explanation: longest common prefix among all strings is "fl".
Example 2
Output: 4
Explanation: The last word is "moon" with length 4.
Example 3
Output: 6
Explanation: The last word is "joyboy" with length 6.
Solution 1 - check character by character from all strings in a vertical fashion
In this approach, we are going to start of with one of the string from strings array as base prefix
-
We will create a function
that takes input argument stringscheckCharsVertically
.strs
-
Create a variable
to keep track of longest prefix length found so far, and take the first element fromlongest
array as base prefix.strs
-
Then, loop through all strings vertically, 1st character in all strings and then 2nd character and so on,
when all strings have a character in common then increment
variable, continue this until one of string have no matching character.longest
-
When a character match is not found in any string or at the end simply return substring from
frombase prefix
and0
indexes.longest
Note:
The reason why we return when a character mismatch found in string and at the end is because when strs
When input array has only one string, then it comes to return statement at the end.
public class LongestCommonPrefix {
static String checkCharsVertically(String[] strs) {
int longest = 0;
String prefix = strs[0];
for(int i=0; i<prefix.length(); i++) {
for(int j=1; j<strs.length; j++) {
if(i == strs[j].length() || prefix.charAt(i) != strs[j].charAt(i)) {
return prefix.substring(0, longest);
}
}
longest++;
}
return prefix.substring(0, longest);
}
}
Complexity Analysis:
Time complexity: Above code runs in O(n * m) time where n
strs
m
Space complexity: O(m) for the prefix we are returning.
Above implementations source code can be found at