Write a function to find the longest common prefix string amongst an array of strings.
方法1:BF, 首先计算两个字符串的prefix,每次用这个prefix与下一个字符串生成新的prefix
效果较差,大数据集直接挂了,代码可读性太差-_-!
1 public String longestCommonPrefix(String[] strs) { 2 // Start typing your Java solution below 3 // DO NOT write main() function 4 String commonPre = null; 5 int commonPreLength = 0; 6 if(strs.length == 0){ 7 return ""; 8 } else if(strs.length == 1){ 9 return strs[0];10 } else {11 String a = strs[0];12 String b = strs[1];13 String abPrefix = findCommonPrefix(a, b);14 int abPrefixSize = abPrefix.length();15 16 int strsSize = strs.length - 2;17 for(int i = 0; i < strsSize; i++){18 String tmp = strs[i + 2];19 int tmpLength = tmp.length();20 if(tmpLength >= abPrefixSize && tmp.substring(0, abPrefixSize).equals(abPrefix))21 continue;22 else if(tmpLength >= abPrefixSize && !tmp.substring(0, abPrefixSize).equals(abPrefix)){23 abPrefix = abPrefix.substring(0, abPrefixSize - 1);24 abPrefixSize = abPrefix.length();25 i--;26 continue;27 } 28 if(tmpLength < abPrefixSize){29 abPrefix = abPrefix.substring(0, tmpLength);30 abPrefixSize = abPrefix.length();31 i--;32 continue;33 }34 35 36 37 }38 return abPrefix;39 }40 }41 42 public String findCommonPrefix(String a, String b){43 int length = Math.min(a.length(), b.length());44 int i;45 for(i = 0; i < length; i++){46 if(a.charAt(i) != b.charAt(i)){47 break;48 }49 }50 return a.substring(0, i);51 }
refactor code, 但BF的时间复杂度仍然有O(n^2)
1 public String longestCommonPrefix(String[] strs) { 2 String compare = ""; 3 if(strs.length == 0) 4 return compare; 5 6 compare = strs[0]; 7 for(int i = 1; i < strs.length; i++){ 8 int j = 0; 9 while(j < compare.length() && j < strs[i].length()){10 if(compare.charAt(j) != strs[i].charAt(j)){11 break;12 }13 j++;14 }15 compare = strs[i].substring(0, j);16 }17 return compare;18 }
方法二:依次比较每个字符串的相应位置的字符,直到遇到不匹配项。可以减少不必要的比较
1 public String longestCommonPrefix(String[] strs) { 2 String compare = ""; 3 if(strs.length == 0) 4 return compare; 5 6 int k = 0; 7 while(true){ 8 if(k == strs[0].length()) 9 break;10 char p = strs[0].charAt(k); 11 int i;12 for(i = 1; i < strs.length; i++){13 if(k == strs[i].length())14 break;15 16 if(p != strs[i].charAt(k)){17 break;18 }19 }20 21 if(i != strs.length)22 break;23 24 compare += p;25 k++;26 }27 28 return compare;29 }
refactor code
1 public String longestCommonPrefix(String[] strs) { 2 String compare = ""; 3 if(strs.length == 0) 4 return compare; 5 6 int k = 0; 7 while(true){ 8 char p = ' '; 9 int i;10 for(i = 0; i < strs.length; i++){11 12 if(k == strs[i].length())13 break;14 15 if(i == 0){16 p = strs[i].charAt(k);17 }18 19 if(p != strs[i].charAt(k)){20 break;21 }22 }23 24 if(i != strs.length)25 break;26 27 compare += p;28 k++;29 }30 31 return compare;32 }