14 Longest Common Prefix

14 Longest Common Prefix

从string array中寻找最长公共前缀。

flowey flower  -> flowe (flower都不会写了只会写flowey  undertale病犯了)

所有字母都以小写形式给出。

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {pty()) return "";if(strs.size() == 1) return strs[0];string prefix = commonPrefix(strs[1], strs[0]);int size = strs.size();for(int i = 2; i< size; i++){prefix = commonPrefix(prefix, strs[i]);}return prefix;}string commonPrefix(string str1, string str2){string prefix = "";int len = max(str1.size(), str2.size());for(int i = 0; i< len; i++){if(str1[i] == str2[i]){prefix += str1[i];}else break;}return prefix;}
};

执行用时 : 16 ms, 在Longest Common Prefix的C++提交中击败了11.93% 的用户

内存消耗 : 10 MB, 在Longest Common Prefix的C++提交中击败了0.90% 的用户

 注意， 数组为空的情况和数组元素为1 的情况需要特殊考虑。也就是说，写完程序之后，要考虑输入的特殊情况。 时间复杂度为 m*n

评论给的五种思路：

1、所求的最长公共前缀子串一定是每个字符串的前缀子串。所以随便选择一个字符串作为标准，把它的前缀串，与其他所有字符串进行判断，看是否是它们所有人的前缀子串。这里的时间性能是O(m*n*m)。

2、列出所有的字符串的前缀子串，将它们合并后排序，找出其中个数为n且最长的子串。时间性能为O(n*m+m*n*log(m*n))

3、纵向扫描：从下标0开始，判断每一个字符串的下标0，判断是否全部相同。直到遇到不全部相同的下标。时间性能为O(n*m)。

4、横向扫描：前两个字符串找公共子串，将其结果和第三个字符串找公共子串……直到最后一个串。时间性能为O(n*m)。

5、借助trie字典树。将这些字符串存储到trie树中。那么trie树的第一个分叉口之前的单分支树的就是所求。

排行上执行为4ms的范例    

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {string common_for = "";size_t common_len = 0;if (pty())   return common_for;for (auto iter = strs.cbegin();iter != d();++iter){if (iter == strs.cbegin()) {common_for = *iter;common_len = common_for.length();continue;}common_len = common_len < iter->length() ? common_len : iter->length();for (int i = 0;i < common_len;++i) {if (common_for[i] != (*iter)[i]) {common_len = i;break;}}}return ase(common_len);}
};

话说这思路和我一样啊。。但是灵活运用的迭代器，值得去学习。