跳转至

词典中最长的单词⚓︎

Leetcode题目链接

描述⚓︎

详见中文题目链接。

解答⚓︎

 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
class Solution {
private:
    vector<vector<int>> son;
    vector<int> cnt;
    int idx;
    void insert(string& word) {
        int p = 0;
        for (char s : word) {
            int u = s - 'a';
            if (!son[p][u]) son[p][u] = ++idx;
            p = son[p][u];
        }
        cnt[p]++;
    }
    int query(string& word) {
        int p = 0;
        for (char s : word) {
            int u = s - 'a';
            p = son[p][u];
            if (!p || cnt[p] == 0) return 0;
        }
        return cnt[p];
    }
public:
    string longestWord(vector<string>& words) {
        son = vector<vector<int>>(30010, vector<int>(26, 0));
        cnt = vector<int>(30010, 0);
        idx = 0;
        set<string> ans;
        for (string word : words) insert(word);
        for (string word : words) {
            if (query(word) > 0) ans.insert(word);
        }

        string longest = "";
        for (string word : ans) {
            if (word.length() > longest.length() || ((word.length() == longest.length() && word < longest)))
            longest = word;
        }

        return longest;
    }
};