题解 | #最长公共前缀#

题意思路：

题目给出长度为n的子串，找出子串中最长的公共前缀。

方法一：子串纵向查找

纵向遍历非常的直观，如下图所示，将每个字符串分别依次遍历每一列的元素，比较相同列上字符是否相同，若相同则比较下一个子串，若不同则最长公共前缀为上个遍历过的公共前缀。

复杂度分析：
时间复杂度：O(mn)，其中n 是字符串的数量，m 是字符串数组中的字符串的平均长度。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

空间复杂度：O(1)。额外空间复杂度为常数。

演示子串纵向查找方式：

class Solution {
public:

    string longestCommonPrefix(vector<string>& strs) {
        // write code here
        if(!strs.size())return "";//特判若子串为空则返回空值
        for(int i=0;i<strs[0].size();i++){//枚举第一个子串的每个字符
            for(int j=1;j<strs.size();j++){//枚举后面所有子串
                if(strs[0][i]!=strs[j][i]||i==strs[j].size()){//比较后面所有子串的第i列字符和第j个子串的长度
                    return strs[0].substr(0,i);//若字符不相同或者长度为最小则返回最长公共前缀
                }
            }
        }
        return strs[0];
    }
};

方法二：排序后子串纵向查找

先将所以子字符串按照字典序的大小排序，想要得到最长公共前缀，只需要将字典序最小的子串A与字典序最大的B比较相同部分，得到的最长公共前缀就是所有子串的公共前缀。

复杂度分析：

时间复杂度：O(nlogn)，其中n 是字符串的数量，排序算法时间复杂度O(nlogn)。

空间复杂度：O(1)。额外空间复杂度为常数。

class Solution {
public:

    string longestCommonPrefix(vector<string>& strs) {
         if(!strs.size())return "";
         sort(strs.begin(),strs.end());//按照字典序排序得到所有子串顺序
         string a=strs.front(),b=strs.back();//枚举第一个最小的子串和最后一个最大的子串
         int i=0;
         for(i=0;i<a.size()&&a[i]==b[i];i++);//若字符相同则继续比较否则返回最长公共前缀串
         return a.substr(0,i);

    }
};