题解 | #最长公共前缀#

题目主要信息:

• 给定一个字符串数组，其中有n个字符串，求所有字符串的最长公共前缀
• 公共前缀是指所有字符串都共有的前面部分的子串，从第一个字符开始

具体思路:

既然是公共前缀，那我们可以从第一个字符开始，逐位比较，找到最长公共子串。

• step 1：处理数组为空的特殊情况。
• step 2：因为最长公共前缀的长度不会超过任何一个字符串的长度，因此我们逐位就以第一个字符串为标杆，遍历第一个字符串的所有位置，取出字符。
• step 3：遍历数组中后续字符串，依次比较其他字符串中相应位置是否为刚刚取出的字符，如果是，循环继续，继续查找，如果不是或者长度不足，说明从第i位开始不同，前面的都是公共前缀。
• step 4：如果遍历结束都相同，最长公共前缀最多为第一个字符串。

具体过程如下图所示：

代码实现:

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int n = strs.size();
        if(n == 0) //空字符串数组
            return "";
        for(int i = 0; i < strs[0].length(); i++){ //遍历第一个字符串的长度
            char temp = strs[0][i]; 
            for(int j = 1; j < n; j++) //遍历后续的字符串
                if(i == strs[j].length() || strs[j][i] != temp) //比较每个字符串该位置是否和第一个相同
                    return strs[0].substr(0, i); //不相同则结束
        }
        return strs[0]; //后续字符串有整个字一个字符串的前缀
    }
};

复杂度分析：

• 时间复杂度：$O(mn)O(mn)$，其中$mm$为数组中最短的字符串的长度，$nn$为字符串数组的长度，两层遍历循环
• 空间复杂度：$O(1)O(1)$，没有使用额外的辅助空间