14. 最长公共前缀

1.题目：https://leetcode-cn.com/problems/longest-common-prefix/

2.思路

（1）最长前缀公共子串，表明了：所有字符串中取最小的，那么就是最长的公共子串了
找到最短字符串，以它的长度为基准，从所有字符串的第一个字符开始对比，若都一样，ans加上该字符，若不一样，返回答案；

（2）其它方法：
大概有这四种思路, 一般都会采用第四种, 但是耗时太多

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

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

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

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

有实现：https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode/

3.代码

https://leetcode-cn.com/problems/longest-common-prefix/solution/cxiang-xi-ti-jie-by-youlookdeliciousc-5/
class Solution {
public:
    string longestCommonPrefix(vector& strs) {
        string strs1="";
        
        if (strs.empty())
            return strs1;
        
        int length =strs.size();
        string min=strs[0];
        for (int i=0;i        {
            if (strs[i].size()                min=strs[i];
        }
        
        for (int j=0;j        {
            for (int i=0;i            {
                if (min[j]!=strs[i][j])
                    return strs1;
            }
            strs1=strs1+min[j];
        }
        return strs1;
    }
};

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net