Leetcode: Longest Common Prefix

题意

给定几个字符串, 求解这几个字符串的公共前序

思路

最朴素的思路是一列一列的比较, 时间复杂度为 n*m, 其中n为字符串的个数, m为公共前序的长度
每一列进行比较的时候, 可以使用分治法. 时间复杂度下降到 logn *m

总结

我最讨厌的便是分支语句. MergeSort 的分支有必要记一下, 当集合小于等于3时不再继续划分. 还要注意边际条件

代码

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 using namespace std;
 5 class Solution {
 6 public:
 7     bool allEqual(vector<string> &strs, int ith, int from, int to) {
 8         if(to-from == 2) {
 9             if(strs[from][ith] == strs[from+1][ith] && strs[from][ith] == strs[to][ith])
10                 return true;
11             return false;
12         }else if(to-from == 1) {
13             if(strs[from][ith] == strs[to][ith])
14                 return true;
15             return false;
16         }else if(to-from == 0) {
17             return true;
18         }
19         int mid = (from+to)>>1;
20         return (allEqual(strs, ith, from, mid) && allEqual(strs, ith, mid+1, to));
21     }
22     string longestCommonPrefix(vector<string> &strs) {
23         int vec_size = strs.size();
24         if(vec_size == 0)
25             return "";
26         else if(vec_size == 1) {
27             return strs[0];
28         }
29         int minSize = 0x3fffffff;
30         for(int i = 0; i < strs.size(); i ++) {
31             minSize = min(minSize, (int)strs[i].size());
32         }
33         int i =0;
34         
35         for(; i < minSize; i ++) {
36             if(!allEqual(strs, i, 0, vec_size-1))
37                 break;
38         }
39         return strs[0].substr(0, i);
40     }
41 };

update 2014年2月20日20:18:39

自己二逼了，这道题 merge 没有意义的