1
插入单词: ["apple", "app", "ape", "bat", "bad", "ban"]
2

3
          (root)
4
         /      \
5
        a        b
6
        |        |
7
        p        a
8
       / \      / | \
9
      p   e    t   d   n
10
      |   ■    ■   ■   ■
11
      l
12
      |
13
      e
14
      ■
15

16
■ = 标记"这里结束了一个完整单词"
17
  "app" 在 p-p 处标记 ■
18
  "ape" 在 p-e 处标记 ■
19
  "apple" 在 l-e 处标记 ■

1
方式一: 固定数组 children[26]  (只支持小写字母)
2
  ┌───────────────────────────────────────────────┐
3
  │ TrieNode                                      │
4
  │   children[0] (a) → nullptr                   │
5
  │   children[1] (b) → TrieNode*                 │
6
  │   children[2] (c) → nullptr                   │
7
  │   ...                                         │
8
  │   children[25] (z) → nullptr                  │
9
  │   is_end = false                              │
10
  └───────────────────────────────────────────────┘
11
  优点: O(1) 随机访问子节点
12
  缺点: 每个节点 26 个指针, 大量 nullptr 浪费内存
13

14
方式二: 哈希表 unordered_map<char, TrieNode*>
15
  ┌───────────────────────────────────────────────┐
16
  │ TrieNode                                      │
17
  │   children = { 'b' → TrieNode*, 'x' → ... }  │
18
  │   is_end = false                              │
19
  └───────────────────────────────────────────────┘
20
  优点: 只存实际存在的子节点, 节省内存
21
  缺点: 哈希表查找常数略大, 不支持字典序遍历(除非用 map)

1
#include <string>
2
#include <vector>
3

4
class Trie {
5
    struct TrieNode {
6
        TrieNode* children[26] = {};  // 初始化为 nullptr
7
        bool is_end = false;          // 是否是某个单词的结尾
8
        // int count = 0;             // 可选: 以此为前缀的单词数
9
    };
10

11
    TrieNode* _root;
12

13
public:
14
    Trie() : _root(new TrieNode()) {}
15

16
    ~Trie() { _destroy(_root); }
17

18
    // ========== 插入单词 ==========
19
    void insert(const std::string& word) {
20
        TrieNode* node = _root;
21
        for (char c : word) {
22
            int idx = c - 'a';
23
            if (!node->children[idx]) {
24
                node->children[idx] = new TrieNode();
25
            }
26
            node = node->children[idx];
27
        }
28
        node->is_end = true;  // 标记单词结尾
29
    }
30

31
    // ========== 查找单词 (精确匹配) ==========
32
    bool search(const std::string& word) const {
33
        const TrieNode* node = _find_node(word);
34
        return node != nullptr && node->is_end;
35
    }
36

37
    // ========== 前缀查询 ==========
38
    bool startsWith(const std::string& prefix) const {
39
        return _find_node(prefix) != nullptr;
40
    }
41

42
private:
43
    // 沿着 key 的字符路径走到对应节点
44
    const TrieNode* _find_node(const std::string& key) const {
45
        const TrieNode* node = _root;
46
        for (char c : key) {
47
            int idx = c - 'a';
48
            if (!node->children[idx]) return nullptr;
49
            node = node->children[idx];
50
        }
51
        return node;
52
    }
53

54
    void _destroy(TrieNode* node) {
55
        if (!node) return;
56
        for (auto* child : node->children) {
57
            _destroy(child);
58
        }
59
        delete node;
60
    }
61
};

1
#include <string>
2
#include <unordered_map>
3

4
class TrieMap {
5
    struct TrieNode {
6
        std::unordered_map<char, TrieNode*> children;
7
        bool is_end = false;
8
    };
9

10
    TrieNode* _root;
11

12
public:
13
    TrieMap() : _root(new TrieNode()) {}
14

15
    void insert(const std::string& word) {
16
        TrieNode* node = _root;
17
        for (char c : word) {
18
            if (node->children.find(c) == node->children.end()) {
19
                node->children[c] = new TrieNode();
20
            }
21
            node = node->children[c];
22
        }
23
        node->is_end = true;
24
    }
25

26
    bool search(const std::string& word) const {
27
        const TrieNode* node = _find(word);
28
        return node && node->is_end;
29
    }
30

31
    bool startsWith(const std::string& prefix) const {
32
        return _find(prefix) != nullptr;
33
    }
34

35
    // 收集以 prefix 开头的所有单词 (自动补全)
36
    std::vector<std::string> autocomplete(const std::string& prefix,
37
                                          int max_results = 10) const
38
    {
39
        const TrieNode* node = _find(prefix);
40
        if (!node) return {};
41

42
        std::vector<std::string> results;
43
        std::string current = prefix;
44
        _collect(node, current, results, max_results);
45
        return results;
46
    }
47

48
private:
49
    const TrieNode* _find(const std::string& key) const {
50
        const TrieNode* node = _root;
51
        for (char c : key) {
52
            auto it = node->children.find(c);
53
            if (it == node->children.end()) return nullptr;
54
            node = it->second;
55
        }
56
        return node;
57
    }
58

59
    // DFS 收集所有完整单词
60
    void _collect(const TrieNode* node, std::string& current,
61
                  std::vector<std::string>& results, int max) const
62
    {
63
        if (static_cast<int>(results.size()) >= max) return;
64

65
        if (node->is_end) {
66
            results.push_back(current);
67
        }
68

69
        for (auto& [c, child] : node->children) {
70
            current.push_back(c);
71
            _collect(child, current, results, max);
72
            current.pop_back();
73
        }
74
    }
75
};

1
class CountTrie {
2
    struct TrieNode {
3
        TrieNode* children[26] = {};
4
        int pass_count = 0;  // 经过这个节点的单词数
5
        int end_count = 0;   // 在这个节点结束的单词数
6
    };
7

8
    TrieNode* _root;
9

10
public:
11
    CountTrie() : _root(new TrieNode()) {}
12

13
    void insert(const std::string& word) {
14
        TrieNode* node = _root;
15
        node->pass_count++;
16
        for (char c : word) {
17
            int idx = c - 'a';
18
            if (!node->children[idx]) {
19
                node->children[idx] = new TrieNode();
20
            }
21
            node = node->children[idx];
22
            node->pass_count++;
23
        }
24
        node->end_count++;
25
    }
26

27
    // 删除一个单词 (支持重复插入)
28
    void erase(const std::string& word) {
29
        if (count_word(word) == 0) return;  // 不存在
30

31
        TrieNode* node = _root;
32
        node->pass_count--;
33
        for (char c : word) {
34
            int idx = c - 'a';
35
            node->children[idx]->pass_count--;
36
            if (node->children[idx]->pass_count == 0) {
37
                // 后续子树没有任何单词经过了, 直接删除
38
                _destroy(node->children[idx]);
39
                node->children[idx] = nullptr;
40
                return;
41
            }
42
            node = node->children[idx];
43
        }
44
        node->end_count--;
45
    }
46

47
    // 查询某个单词出现了几次
48
    int count_word(const std::string& word) const {
49
        const TrieNode* node = _find(word);
50
        return node ? node->end_count : 0;
51
    }
52

53
    // 查询以某个前缀开头的单词有几个
54
    int count_prefix(const std::string& prefix) const {
55
        const TrieNode* node = _find(prefix);
56
        return node ? node->pass_count : 0;
57
    }
58

59
private:
60
    const TrieNode* _find(const std::string& key) const {
61
        const TrieNode* node = _root;
62
        for (char c : key) {
63
            int idx = c - 'a';
64
            if (!node->children[idx]) return nullptr;
65
            node = node->children[idx];
66
        }
67
        return node;
68
    }
69

70
    void _destroy(TrieNode* node) {
71
        if (!node) return;
72
        for (auto* child : node->children) _destroy(child);
73
        delete node;
74
    }
75
};

1
Step 1: 暴力想法
2
  对每个单词, 从网格的每个格子出发做 DFS → O(W × m×n × 4^L)
3
  如果有 W=1000 个单词, 每个做一次完整 DFS → 太慢
4

5
Step 2: 瓶颈在哪？
6
  瓶颈是 "W 次独立的 DFS"。
7
  能不能一次 DFS 就同时检查所有单词?
8

9
Step 3: 关键洞察 → 前缀共享
10
  如果多个单词有相同前缀 (如 "oath" 和 "oat"),
11
  DFS 走 o→a→t 这条路径时, 可以同时检查两个单词!
12

13
  "共享前缀 + 路径查找" → 这就是 Trie!
14

15
Step 4: 方案
16
  1. 所有单词建入 Trie
17
  2. 从网格每个格子出发 DFS, 同时在 Trie 上移动
18
  3. 如果 Trie 当前节点没有对应子节点 → 剪枝! (这个前缀不可能匹配任何单词)
19
  4. 如果到达 Trie 中某个 is_end 节点 → 找到一个单词!
20

21
Step 5: 优化
22
  - 找到单词后设 word=nullptr 去重 (同一个单词只记一次)
23
  - 用 '#' 标记已访问格子 (回溯时恢复)
24
  - 可以动态剪去已匹配完的 Trie 分支, 进一步加速

1
class Solution {
2
    struct TrieNode {
3
        TrieNode* children[26] = {};
4
        std::string* word = nullptr;  // 到达此节点时的完整单词
5

6
        ~TrieNode() {
7
            for (auto* child : children) delete child;
8
        }
9
    };
10

11
    TrieNode* _root;
12

13
    void _build_trie(std::vector<std::string>& words) {
14
        _root = new TrieNode();
15
        for (auto& w : words) {
16
            TrieNode* node = _root;
17
            for (char c : w) {
18
                int idx = c - 'a';
19
                if (!node->children[idx]) {
20
                    node->children[idx] = new TrieNode();
21
                }
22
                node = node->children[idx];
23
            }
24
            node->word = &w;  // 指向原始单词 (避免复制)
25
        }
26
    }
27

28
    void _dfs(std::vector<std::vector<char>>& board,
29
              int i, int j, TrieNode* node,
30
              std::vector<std::string>& result)
31
    {
32
        if (i < 0 || i >= static_cast<int>(board.size())
33
            || j < 0 || j >= static_cast<int>(board[0].size()))
34
            return;
35

36
        char c = board[i][j];
37
        if (c == '#') return;  // 已访问
38

39
        int idx = c - 'a';
40
        if (!node->children[idx]) return;  // Trie 中没有这个前缀 → 剪枝!
41

42
        node = node->children[idx];
43

44
        if (node->word) {
45
            result.push_back(*node->word);
46
            node->word = nullptr;  // 去重: 一个单词只加一次
47
        }
48

49
        // DFS 四个方向
50
        board[i][j] = '#';  // 标记已访问
51
        _dfs(board, i + 1, j, node, result);
52
        _dfs(board, i - 1, j, node, result);
53
        _dfs(board, i, j + 1, node, result);
54
        _dfs(board, i, j - 1, node, result);
55
        board[i][j] = c;    // 回溯: 恢复
56

57
        // 优化: 如果当前节点已无子节点, 从 Trie 中剪掉
58
        // (后续不会再有单词经过这里)
59
    }
60

61
public:
62
    std::vector<std::string> findWords(
63
        std::vector<std::vector<char>>& board,
64
        std::vector<std::string>& words)
65
    {
66
        _build_trie(words);
67

68
        std::vector<std::string> result;
69
        int m = board.size(), n = board[0].size();
70

71
        for (int i = 0; i < m; ++i) {
72
            for (int j = 0; j < n; ++j) {
73
                _dfs(board, i, j, _root, result);
74
            }
75
        }
76

77
        delete _root;
78
        return result;
79
    }
80
};
81
// 时间 O(m × n × 4^L), L = 最长单词长度
82
// 实际远快于暴力, 因为 Trie 前缀剪枝砍掉了大量无效搜索

1
class AutocompleteSystem {
2
    struct TrieNode {
3
        std::unordered_map<char, TrieNode*> children;
4
        std::unordered_map<std::string, int> sentences;
5
        // 经过此节点的所有句子及其热度
6
    };
7

8
    TrieNode* _root;
9
    TrieNode* _current;   // 当前输入位置
10
    std::string _input;   // 当前输入缓冲
11

12
public:
13
    AutocompleteSystem(std::vector<std::string>& sentences,
14
                       std::vector<int>& times)
15
    {
16
        _root = new TrieNode();
17
        _current = _root;
18

19
        for (int i = 0; i < static_cast<int>(sentences.size()); ++i) {
20
            _insert(sentences[i], times[i]);
21
        }
22
    }
23

24
    std::vector<std::string> input(char c) {
25
        if (c == '#') {
26
            // 输入结束, 记录当前输入的句子
27
            _insert(_input, 1);
28
            _input.clear();
29
            _current = _root;
30
            return {};
31
        }
32

33
        _input += c;
34

35
        // 在 Trie 上移动
36
        if (_current && _current->children.count(c)) {
37
            _current = _current->children[c];
38
        } else {
39
            _current = nullptr;  // 无匹配
40
            return {};
41
        }
42

43
        // 找热度最高的 3 个
44
        auto& candidates = _current->sentences;
45
        std::vector<std::pair<std::string, int>> sorted(
46
            candidates.begin(), candidates.end());
47

48
        std::sort(sorted.begin(), sorted.end(),
49
            [](const auto& a, const auto& b) {
50
                return a.second > b.second
51
                    || (a.second == b.second && a.first < b.first);
52
            });
53

54
        std::vector<std::string> result;
55
        for (int i = 0; i < 3 && i < static_cast<int>(sorted.size()); ++i) {
56
            result.push_back(sorted[i].first);
57
        }
58
        return result;
59
    }
60

61
private:
62
    void _insert(const std::string& sentence, int times) {
63
        TrieNode* node = _root;
64
        for (char c : sentence) {
65
            if (!node->children.count(c)) {
66
                node->children[c] = new TrieNode();
67
            }
68
            node = node->children[c];
69
            node->sentences[sentence] += times;  // 每个路径节点都记录完整句子
70
        }
71
    }
72
};

1
class WordDictionary {
2
    struct TrieNode {
3
        TrieNode* children[26] = {};
4
        bool is_end = false;
5
    };
6

7
    TrieNode* _root;
8

9
public:
10
    WordDictionary() : _root(new TrieNode()) {}
11

12
    void addWord(const std::string& word) {
13
        TrieNode* node = _root;
14
        for (char c : word) {
15
            int idx = c - 'a';
16
            if (!node->children[idx]) {
17
                node->children[idx] = new TrieNode();
18
            }
19
            node = node->children[idx];
20
        }
21
        node->is_end = true;
22
    }
23

24
    bool search(const std::string& word) {
25
        return _dfs(_root, word, 0);
26
    }
27

28
private:
29
    bool _dfs(TrieNode* node, const std::string& word, int pos) {
30
        if (!node) return false;
31
        if (pos == static_cast<int>(word.size())) return node->is_end;
32

33
        char c = word[pos];
34

35
        if (c == '.') {
36
            // 通配符: 尝试所有子节点
37
            for (int i = 0; i < 26; ++i) {
38
                if (_dfs(node->children[i], word, pos + 1)) {
39
                    return true;
40
                }
41
            }
42
            return false;
43
        } else {
44
            return _dfs(node->children[c - 'a'], word, pos + 1);
45
        }
46
    }
47
};
48
// 时间: addWord O(m), search O(m) 无通配, O(26^k × m) 有 k 个通配

1
class Solution {
2
    struct TrieNode {
3
        TrieNode* children[26] = {};
4
        int word_idx = -1;  // 如果某个逆序单词在此结束
5
        std::vector<int> palindrome_below;  // 后续子树中构成回文的单词下标
6
    };
7

8
    TrieNode* _root;
9

10
    bool _is_palindrome(const std::string& s, int left, int right) {
11
        while (left < right) {
12
            if (s[left++] != s[right--]) return false;
13
        }
14
        return true;
15
    }
16

17
public:
18
    std::vector<std::vector<int>> palindromePairs(std::vector<std::string>& words) {
19
        _root = new TrieNode();
20

21
        // 1. 所有单词逆序插入 Trie
22
        for (int i = 0; i < static_cast<int>(words.size()); ++i) {
23
            TrieNode* node = _root;
24
            const auto& w = words[i];
25

26
            for (int j = w.size() - 1; j >= 0; --j) {
27
                // 如果 w[0..j] 是回文, 记录下标
28
                if (_is_palindrome(w, 0, j)) {
29
                    node->palindrome_below.push_back(i);
30
                }
31

32
                int idx = w[j] - 'a';
33
                if (!node->children[idx]) {
34
                    node->children[idx] = new TrieNode();
35
                }
36
                node = node->children[idx];
37
            }
38
            node->word_idx = i;
39
            node->palindrome_below.push_back(i);  // 空串也是回文
40
        }
41

42
        // 2. 对每个单词, 在 Trie 上查找回文对
43
        std::vector<std::vector<int>> result;
44

45
        for (int i = 0; i < static_cast<int>(words.size()); ++i) {
46
            TrieNode* node = _root;
47
            const auto& w = words[i];
48

49
            for (int j = 0; j < static_cast<int>(w.size()); ++j) {
50
                // 当前 Trie 节点是某个逆序单词的结尾
51
                // 且 w 剩余部分 w[j..end] 是回文
52
                if (node->word_idx != -1 && node->word_idx != i
53
                    && _is_palindrome(w, j, w.size() - 1))
54
                {
55
                    result.push_back({i, node->word_idx});
56
                }
57

58
                int idx = w[j] - 'a';
59
                if (!node->children[idx]) {
60
                    node = nullptr;
61
                    break;
62
                }
63
                node = node->children[idx];
64
            }
65

66
            if (!node) continue;
67

68
            // w 完全匹配了 Trie 路径, 检查后续回文子树
69
            for (int j : node->palindrome_below) {
70
                if (j != i) {
71
                    result.push_back({i, j});
72
                }
73
            }
74
        }
75

76
        return result;
77
    }
78
};
79
// 时间 O(n × m²), n = 单词数, m = 最长单词长度

1
// Trie 解法: 所有字符串插入 Trie, 从根走到第一个分叉点
2
std::string longestCommonPrefix(std::vector<std::string>& strs) {
3
    if (strs.empty()) return "";
4

5
    Trie trie;
6
    for (auto& s : strs) {
7
        if (s.empty()) return "";
8
        trie.insert(s);
9
    }
10

11
    // 从根开始, 沿着唯一子节点走, 直到分叉或遇到单词结尾
12
    std::string prefix;
13
    auto* node = trie.root();  // 假设 Trie 暴露了 root()
14

15
    while (true) {
16
        int child_count = 0, child_idx = -1;
17
        for (int i = 0; i < 26; ++i) {
18
            if (node->children[i]) {
19
                ++child_count;
20
                child_idx = i;
21
            }
22
        }
23

24
        // 分叉 (>1 个子节点) 或到达某个单词结尾 → 停止
25
        if (child_count != 1 || node->is_end) break;
26

27
        prefix += static_cast<char>('a' + child_idx);
28
        node = node->children[child_idx];
29
    }
30

31
    return prefix;
32
}

1
// 游戏中的聊天系统, 需要实时过滤敏感词
2
// 方案: 将所有敏感词建入 Trie, 对用户输入逐字符在 Trie 上匹配
3

4
class SensitiveWordFilter {
5
    struct TrieNode {
6
        TrieNode* children[128] = {};  // 支持 ASCII
7
        bool is_end = false;
8
        int word_length = 0;  // 匹配到时需要替换的长度
9
    };
10

11
    TrieNode* _root;
12

13
public:
14
    SensitiveWordFilter() : _root(new TrieNode()) {}
15

16
    // 添加敏感词
17
    void add_word(const std::string& word) {
18
        TrieNode* node = _root;
19
        for (char c : word) {
20
            if (!node->children[static_cast<int>(c)]) {
21
                node->children[static_cast<int>(c)] = new TrieNode();
22
            }
23
            node = node->children[static_cast<int>(c)];
24
        }
25
        node->is_end = true;
26
        node->word_length = word.size();
27
    }
28

29
    // 过滤: 将敏感词替换为 ***
30
    std::string filter(const std::string& text) {
31
        std::string result = text;
32

33
        for (int i = 0; i < static_cast<int>(text.size()); ++i) {
34
            TrieNode* node = _root;
35

36
            for (int j = i; j < static_cast<int>(text.size()); ++j) {
37
                int idx = static_cast<int>(text[j]);
38
                if (!node->children[idx]) break;
39

40
                node = node->children[idx];
41

42
                if (node->is_end) {
43
                    // 命中敏感词! 替换为 ***
44
                    for (int k = i; k <= j; ++k) {
45
                        result[k] = '*';
46
                    }
47
                    // 不 break: 继续匹配更长的敏感词
48
                    // (如 "麻" 和 "麻将" 都是敏感词, 要匹配最长的)
49
                }
50
            }
51
        }
52

53
        return result;
54
    }
55
};
56

57
// 使用:
58
// SensitiveWordFilter filter;
59
// filter.add_word("fuck");
60
// filter.add_word("shit");
61
// filter.add_word("damn");
62
// std::string safe = filter.filter("what the fuck");  // "what the ****"

1
// 游戏内控制台 (如 Minecraft 的 / 命令):
2
// /help  /home  /tp  /teleport  /time  /give  /gamemode
3

4
class ConsoleAutocomplete {
5
    struct TrieNode {
6
        std::unordered_map<char, TrieNode*> children;
7
        std::string full_command;  // 非空表示这是一个完整命令
8
        std::string description;   // 命令描述
9
    };
10

11
    TrieNode* _root;
12

13
public:
14
    ConsoleAutocomplete() : _root(new TrieNode()) {}
15

16
    void register_command(const std::string& command,
17
                          const std::string& desc)
18
    {
19
        TrieNode* node = _root;
20
        for (char c : command) {
21
            if (!node->children.count(c)) {
22
                node->children[c] = new TrieNode();
23
            }
24
            node = node->children[c];
25
        }
26
        node->full_command = command;
27
        node->description = desc;
28
    }
29

30
    // 输入前缀, 返回匹配的命令和描述
31
    struct Suggestion {
32
        std::string command;
33
        std::string description;
34
    };
35

36
    std::vector<Suggestion> suggest(const std::string& prefix) {
37
        TrieNode* node = _root;
38
        for (char c : prefix) {
39
            if (!node->children.count(c)) return {};
40
            node = node->children[c];
41
        }
42

43
        std::vector<Suggestion> results;
44
        _collect(node, results);
45
        return results;
46
    }
47

48
private:
49
    void _collect(TrieNode* node, std::vector<Suggestion>& results) {
50
        if (!node->full_command.empty()) {
51
            results.push_back({node->full_command, node->description});
52
        }
53
        for (auto& [c, child] : node->children) {
54
            _collect(child, results);
55
        }
56
    }
57
};
58

59
// 使用:
60
// ConsoleAutocomplete console;
61
// console.register_command("/teleport", "传送到指定坐标");
62
// console.register_command("/time", "设置时间");
63
// console.register_command("/tp", "传送到玩家 (简写)");
64
//
65
// 玩家输入 "/t" → suggest("/t"):
66
//   ["/teleport - 传送到指定坐标", "/time - 设置时间", "/tp - 传送到玩家"]
67
//
68
// 玩家输入 "/te" → suggest("/te"):
69
//   ["/teleport - 传送到指定坐标"]

1
// 游戏引擎中, 资源路径有大量共享前缀:
2
// "assets/textures/character/hero_01.png"
3
// "assets/textures/character/hero_02.png"
4
// "assets/textures/environment/grass.png"
5
// "assets/textures/environment/sky.png"
6
// "assets/models/character/hero.fbx"
7
// "assets/sounds/bgm/battle.ogg"
8

9
// Trie 优势:
10
// 1. 共享前缀节省内存 ("assets/textures/" 只存一次)
11
// 2. 快速前缀查询: "assets/textures/character/" → 列出所有角色贴图
12
// 3. 热加载: 某个文件夹变化时, 快速定位受影响的资源
13

14
// 本地化 key 查找:
15
// "ui.menu.start"
16
// "ui.menu.settings"
17
// "ui.menu.quit"
18
// "ui.dialog.confirm"
19
// "ui.dialog.cancel"
20
// 用 Trie 按 '.' 分割, 快速获取某个 namespace 下的所有 key