题解 | #最长公共前缀#

最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
输入：["abca","abc","abca","abc","abcc"]
返回值："abc"

方法一 暴力

由题意可得 最长的一定是在最字符串长度最小的一个前缀字符串中,所以取第一个字符串去和全部字符串做对比，只要出现不一样就更新最长长度。

代码:

 string longestCommonPrefix(vector<string>& strs) {
        // write code here
        if(!strs.size()) return "";
        int n = strs.size();
        int xz = strs[0].length();
        for(int i = 1; i < n; i ++){    //从第二个字符串开始全部和第一个做对比
            xz = min(xz, (int)strs[i].length());    //取字符串长度最小的因为大肯定不可能
            for(int j = 0; j < xz; j ++){
                if(strs[0][j] != strs[i][j]){
                    xz = j; break;//如果不同则更新
                }
            }
        }
        return strs[0].substr(0, xz);
    }

时间复杂度: 最坏情况为所有字符串长度一致
空间复杂度: 若干个变量

方法二 贪心

对初始数组做一个排序,然后取第一个和最后一个字符串进行对比,因为字符串进行了字典序排序,差异比较小的会在一起,根据这一性质可以直接对排序后的字符串的第一个和最后一个进行对比即可

string longestCommonPrefix(vector<string>& strs) {
        // write code here
        if(!strs.size()) return "";
        sort(strs.begin(), strs.end());    //默认字符串排序按字典排序
        int i = 0;
        string a = strs.front(), b = strs.back();    //取第一个和最后一个的字符串
        for(; i < min(a.length(), b.length()) && a[i] == b[i]; i ++);    //找出不一样的字母在第几个
        return a.substr(0, i);
    }

时间复杂度: 字符串排序的复杂度
空间复杂度: 使用额外的string存储