Mronne's Blog

最长公共前缀

 
  • 2020年 03月21日

题目

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ”“。

示例 1:

输入: [“flower”,”flow”,”flight”] 输出: “fl”

示例 2:

输入: [“dog”,”racecar”,”car”] 输出: “” 解释: 输入不存在公共前缀。

说明:所有输入只包含小写字母 a-z 。

解法

1.逐个比较法

算法

  • 依次遍历字符串$[S_1,S_2,…,S_n]$
  • 寻找当前的公共前缀与字符串$S_i$的公共前缀prefix
  • 重复此过程直到遍历结束
  • 如果prefix为空，则返回空

代码

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size() == 0) return "";
        string prefix = strs[0];

        for(int i=1;i<strs.size();i++){
          //find 方法 通常达到linear in length()—pos乘以要匹配的序列的长度(最坏情况)。
            while(strs[i].find(prefix) != 0){
                prefix = prefix.substr(0,prefix.size()-1);
                if(prefix.empty()) return "";
            }
        }
        return prefix;
    }
};

复杂度分析

  • 时间复杂度：$O(S)$，S是所有字符串中字符数量的总和。 最坏的情况下，S个字符串都是相同的。算法会将字符串与其他字符串都进行一次比较。
  • 空间复杂度：$O(1)$，使用常数级别的额外空间。 ​

    2.水平扫描法

算法

  • 从前往后枚举字符串的每一列，先比较每个字符串相同列上的字符（即不同字符串相同下标的字符），再对下一列进行比较
  • 停止条件：某个字符串已经遍历完 i==strs[j].size(); 或者遇到不相等字符 strs[j][i] != ch;

代码

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

复杂度分析

  • 时间复杂度：$O(S)$,S是所有字符串中字符数量的总和。

最坏情况：输入数据为 $n$ 个长度为 $m$ 的相同字符串，算法会进行 $S=m \cdot n$ 次比较

最好情况：只需进行$n \cdot minLen$次比较，其中$ minLen $是数组中最短字符串的长度

  • 空间复杂度：$O(1)$，使用常数级别的额外空间。
搜索