LeetCode 14. 最长公共前缀(字典序、前缀树、暴力）_给定一棵带点权树支持加点,询问两条路径最长公共前缀

• 字典序、快排
  一种很巧妙的做法，虽然时间复杂度有点高。
  通过排序，只要比较一前一后两个字符串即可，这个两个字符串有的前缀，那么中间的所有字符串也都有这样的前缀。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0){
            return "";
        }
        if(strs.size()==1){
            return strs[0];
        }
        sort(strs.begin(),strs.end());

        string &s1 = strs[0];
        string &s2 =strs[strs.size()-1];
        int i;
        for(i=0;i<min(s1.size(),s2.size());i++){
            if(s1[i]!=s2[i]){
                break;
            }
        }
        return s1.substr(0,i);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 暴力
  别人的，很简洁，
  时间复杂度$O(n\ast len\ast len)$。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res = strs.empty() ? "" : strs[0]; 
        for (string s : strs) 
            while (s.find(res) != 0) res = res.substr(0, res.length() - 1);
        return res;
    }
};
1
2
3
4
5
6
7
8
9

最简单的暴力法。

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0){
            return "";
        }
        int len = INT_MAX;
        for(string &s:strs){
            len = min(len,(int)s.size());
        }
        string res = strs[0];
        int i;
        for(i=1;i<=len;i++){
            for(string &s:strs){
                if(s.find(res.substr(0,i))!=0){
                    return res.substr(0,i-1);
                }
            }
        }
        return res.substr(0,len);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

• 前缀树
  看到字符串的公共前缀，我就想到了前缀树，虽然此题并不需要。
  思路，每次插入字符串到字典树里面，tot变量加1，这个字符串对应的每个节点值也加1。
  最后，遍历这棵树，求出使得某个深度之前的所有节点的值都是tot,那么这个深度就是最长前缀的长度。
  用深搜来实现。

class Trie{
    struct Node{
        int cnt = 0;
        Node* childs[26] = {0};
    };
    Node *root;
    int tot = 0,depth = 0;
public:
    Trie(){
        root = new Node;
    }
    void insert(string s){
        tot++;
        Node *p = root;
        p->cnt++;
        for(char c:s){
            if(p->childs[c-'a'] ==nullptr){
                p->childs[c-'a'] = new Node;
            }
            p = p->childs[c-'a'];
            p->cnt++;
        }
    }
    int askLargestPrefix(){
        dfs(root,0);
        return depth;
    }
    void dfs(Node *root,int dpt){
        if(!root || root->cnt<tot){
            return;
        }
        depth = max(depth,dpt);
        for(int i=0;i<26;i++){
            dfs(root->childs[i],dpt+1);
        }
    }
};
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs.size()==0){
            return "";
        }
        Trie trie;
        for(string &s:strs){
            trie.insert(s);
        }
        int len = trie.askLargestPrefix();
        return strs[0].substr(0,len);
    }
};


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53