Longest Common Prefix
Problem
Write a function to find the longest common prefix string amongst an array of strings.
The common prefix means prefix in each string
So for ["a", "bc", "bd"]
result is "", cause they don't share a common prefix
Prefix can have more than one character
Solution
Clear Iterative Solution: O(n^2) time
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) != 0) prefix = prefix.substring(0, prefix.length() - 1);
}
return prefix;
}
}
Analysis
We first set prefix
as the first element in given strs
Then we loop from the second element and check if they share common prefix
If not, we reduce the prefix
by dropping the last character in a while
loop
At the end, we return what prefix
left