HOT100 14最长公共前缀

2023-04-07

最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 ““。

思路

暴力比较，两层for循环依次比较每一个字符串的每个字符

代码

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0)
        {
            return "";
        }
        int shortest=INT_MAX;
        for(int i=0;i<strs.size();i++){
            if(strs[i].length()<shortest){
                shortest=strs[i].length();
            }
        }
        vector<int> array(shortest);
        for(int i=0;i<shortest;i++){
            for(int j=0;j<strs.size();j++){
                if(strs[j][i]!=strs[0][i]){
                    array[i]=1;
                    i=shortest;
                    j=strs.size();
                }
            }
        }
        int i=0;
        for(;i<shortest;i++){
            if(array[i]!=0){
                break;
            }
        }
        return strs[0].substr(0,i);
    }
};

执行用时：8 ms, 在所有 C++ 提交中击败了28.37%的用户
内存消耗：9 MB, 在所有 C++ 提交中击败了52.17%的用户
通过测试用例：124 / 124

评论