[LeetCode] Longest Common Prefix 解题报告

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

» Solve this problem

[解题报告]
又一个实现题。遍历字符串数组，每次用当前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:    }  

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

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

Update 2, 3/7/2013
refactor code  a bit

1:     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:       }