Solving any problem requires one to analyze various available solutions and then look at factors like space complexity, time complexity, and ease of development.
Problem statement: Find the longest common prefix from N number of Strings.
Example: “kamal”, “kamalmeet”, “kamaljeet” should return “kamal”
Solution 1- Vertical Scanning
Approach: Start with the first element of each string and compare for equality. Continue till a point we do not find the same character.
Pseudo code:
-- for i=0 to n, of the length of the first (any) string ---- check if ith character is equal for all string ------ if not, return string from 0 to i-1 character
Code:
public String longestCommonPrefix(String[] strs) {
for (int index = 0; index < strs[0].length(); index++) {
char ch = strs[0].charAt(index);
for (String st : strs) {
// one of the strings has ended or char mismatch found
if (index >= st.length() || st.charAt(index) != ch) {
return strs[0].substring(0, index);
}
}
}
// if you reached here, first string is longest common prefix
return strs[0];
}Time Complexity: O(S) for Worst case all strings are equal, and S is the sum of all string lengths
Space Complexity: O(1) no additional data structure
Solution 2 – Horizontal Scanning
Approach: Start by comparing the first two strings and find the longest common prefix. Use this as input and compare it with next string and so on.
Pseudo code:
-- longestprefix = str[0] -- for strings in i=1 to N ---- longestprefix = findlongestprefix(longestprefix, str[i]) -- return longestprefix
Time Complexity: O(S)
Space complexity: O(1)
Solution 3- Divide and Conquer
Approach: Break down the array of strings into two equal parts, solve for the two subarrays, and find a solution for two results (repeat the process at each step).
Additional Approaches