Solution:
Use first String in the array as reference, compare all other arrays with it char by char. If any string has disagree char, return the current prefix, other wise add the processing char to the result common prefix.
Time complexity:O(m*n) m is Array Length, n is the prefix length.
public String longestCommonPrefix(String[] strs) {
if(strs==null || strs.length==0) return "";
StringBuilder sb=new StringBuilder();
for(int i=0;i<strs[0].length();i++){
for(int j=1;j<strs.length;j++){
if(i>=strs[j].length()) return sb.toString();
if(strs[j].charAt(i)!=strs[0].charAt(i)) return sb.toString();
}
sb.append(strs[0].charAt(i));
}
return sb.toString();
}
No comments:
Post a Comment