最长公共前缀

1
class Solution {
2
public:
3
    string longestCommonPrefix(vector<string>& strs) {
4
        if(strs.empty()) return "";
5

6
        for (int i = 0; i < strs[0].size(); ++i) {
7
            char c = strs[0][i];
8
            for (int j = 1; j < strs.size(); ++j) {
9
                // 如果当前字符串长度不够，或者字符不匹配，就返回当前前缀
10
                if (i >= strs[j].size() || strs[j][i] != c) {
11
                    return strs[0].substr(0, i);
12
                }
13
            }
14
        }
15
        return strs[0];
16
    }
17
};

1
struct TrieNode {
2
    TrieNode* next[26] = {nullptr};
3
    int pass = 0; // 经过该节点的单词数
4
};
5

6
class Solution {
7
public:
8
    string longestCommonPrefix(vector<string>& strs) {
9
        if (strs.empty()) return "";
10
        TrieNode* root = new TrieNode();
11
        const int n = strs.size();
12

13
        // 1. 建树
14
        for (auto &s : strs) {
15
            TrieNode* p = root;
16
            for (char c : s) {
17
                int idx = c - 'a';
18
                if (!p->next[idx]) p->next[idx] = new TrieNode();
19
                p = p->next[idx];
20
                p->pass++;
21
            }
22
        }
23

24
        // 2. 遍历找最长唯一链
25
        string ans;
26
        TrieNode* p = root;
27
        while (true) {
28
            int cnt = 0, idx = -1;
29
            for (int i = 0; i < 26; ++i) {
30
                if (p->next[i]) { cnt++; idx = i; }
31
            }
32
            // 要求：只有一个分支，且该分支被所有单词经过
33
            if (cnt != 1 || p->next[idx]->pass != n) break;
34
            ans += char('a' + idx);
35
            p = p->next[idx];
36
        }
37
        return ans;
38
    }
39
};