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

如果不存在公共前缀,返回空字符串 ""。

 

示例 1:

输入:strs = ["flower","flow","flight"]
输出:"fl"
示例 2:

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

提示:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-common-prefix
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

暴力

k 为 前缀长度

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

时间复杂度: O(n*m^2)
空间复杂度: O(1)

字典树

class Solution {
public:
    struct tier {
        char c;
        tier *next;
    };
    string longestCommonPrefix(vector<string>& strs) {
        tier* t = new tier();
        tier* p = t;
        for(int i = 0; i < strs[0].size(); i++){
            tier* tmp = new tier();
            tmp->c = strs[0][i];
            p->next = tmp;
            p = p->next;
        }
        int mmax = 205;
        for(int i = 1; i < strs.size(); i++){
            p = t->next;
            int j = 0;
            for(; j < strs[i].size(); j++){
                if(!p || strs[i][j] != p->c){
                    break;
                }
                p = p->next;
            }
            mmax = min(mmax, j);
        }
        return strs[0].substr(0, mmax);
    }
};

时间复杂度: O(nm) m是字符串平均长度, n是字符串数量
空间复杂度: O(n)

纵向扫描

class Solution {
public:
    struct tier {
        char c;
        tier *next;
    };
    string longestCommonPrefix(vector<string>& strs) {
        for(int k = 0; k < strs[0].size(); k++){
            for(int i = 1; i < strs.size(); i++){
                if(strs[i][k] != strs[0][k]) {
                    return strs[0].substr(0, k);
                }
            }
        }
        return strs[0];
    }
};

时间复杂度: O(mn) m是字符串平均长度, n是字符串数量

二分答案

最长的公共前缀不会超过数组里最短的字符串 那么最长公共前缀的数量为0~最短字符串长度
check函数则根据提供的前缀长度判断此前缀长度是否是公共前缀
二分则不断逼近最长公共前缀

class Solution {
public:
    bool check(vector<string>& strs, int k){
        for(int i = 0; i < k; i++){
            for(int j = 0; j < strs.size(); j++){
                if(strs[j][i] != strs[0][i]){
                    return false;
                }
            }
        }
        return true;
    }
    string longestCommonPrefix(vector<string>& strs) {
        int left = 0, right = strs[0].size();
        for(int i = 1; i < strs.size(); i++){
            if(right > strs[i].size()){
                right = strs[i].size();
            }
        }

        while(left <= right){
            int mid = (left + right) / 2;
            if(check(strs, mid)){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return strs[0].substr(0, right);
    }
};

标签: none

添加新评论