leetcode -- Longest Common Prefix

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      }