Leet Code 14 Longest Common Prefix

本文主要是介绍Leet Code 14 Longest Common Prefix，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Write a function to find the longest common prefix string amongst an array of strings

【算法思路】

1. 找最短的一个串，然后与其他串每个字符比较

public String longestCommonPrefix(String[] strs) {if(strs.length == 0)return "";if(strs.length == 1)return strs[0];int minLen = strs[0].length();int minIndex = 0;for (int i = 0; i < strs.length; i ++){if (strs[i].length() < minLen){minLen = strs[i].length();minIndex = i;}}StringBuilder sb = new StringBuilder("");for(int i = 0; i < minLen; i ++){int flag = 0;for(int j = 0; j < strs.length; j ++){if(strs[j].charAt(i) != strs[minIndex].charAt(i)){flag = 1;break;}}if(flag == 0){sb.append(strs[minIndex].charAt(i));}else{return sb.toString();}}return sb.toString();}

【CODE V2】

public String longestCommonPrefix(String[] strs) {if(strs == null || strs.length == 0)return "";int minLen=Integer.MAX_VALUE;for(String str: strs){if(minLen > str.length())minLen = str.length();}if(minLen == 0) return "";for(int j=0; j<minLen; j++){char prev='0';for(int i=0; i<strs.length ;i++){if(i==0) {prev = strs[i].charAt(j);continue;}if(strs[i].charAt(j) != prev){return strs[i].substring(0, j);}}}return strs[0].substring(0,minLen);
}

【复杂度】

时间：O(N^2)

空间：O(N)

2. 遍历字符串数组，每次用当前prefix和下一个字符串匹配以生成新的prefix。

[Code]

1:    string longestCommonPrefix(vector<string> &strs) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      string compare;  
5:      if(strs.size() == 0) return compare;  
6:      compare = strs[0];  
7:      for(int i =1; i< strs.size() ; i++)  
8:      {  
9:        string prefix;  
10:        int k =0;  
11:        while(k< compare.size() && k< strs[i].size())  
12:        {  
13:          if(compare[k] != strs[i][k])  
14:            break;  
15:          prefix.append(1, compare[k]);  
16:          k++;  
17:        }  
18:        compare.clear();  
19:        compare.append(prefix.c_str());        
20:      }  
21:      return compare;  
22:    }  

3. 对于每一个字母比较所有字符串，直到遇到任何一个不匹配。这个时间复杂度比上一个解法好一些，避免了不必要的比较。

  string longestCommonPrefix(vector<string> &strs) {  
2:            string prefix;  
3:            if(strs.size() ==0) return prefix;  
4:            int len =0;  
5:            while(1)  
6:            {  
7:                 char var;  
8:                 int i=0;  
9:                 for(; i< strs.size(); i++)  
10:                 {  
11:                      if(i ==0) var =strs[0][len];  
12:                      if(strs[i].size() == len || var != strs[i][len])  
13:                      break;  
14:                 }  
15:                 if(i!= strs.size())  
16:                      break;                 
17:                 len++;  
18:                 prefix.append(1, var);  
19:            }  
20:            return prefix;  
21:       }  

这篇关于Leet Code 14 Longest Common Prefix的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---