• 中文 • Walking in Code

Trie (前缀树) 完全指南 - O(m) 时间复杂度掌握字符串操作

通过交互式可视化掌握 Trie 数据结构。学习 insert、search、startsWith 操作。解决 LeetCode 208、211、212。完整的 JavaScript、Java 和 Python 实现。

#algorithm #trie #prefix-tree #visualization #interview #string #data-structure

什么是 Trie？

Trie（发音同 “try”），也称为前缀树，是一种专为高效字符串操作设计的树形数据结构。与存储完整键的哈希表不同，Trie 在字符串之间共享公共前缀，使其在存储字典类数据时非常节省空间。

面试官为什么喜欢考 Trie

  1. 考察深度理解 - 需要掌握树结构和递归
  2. 优雅的前缀操作 - startsWith 变得极其简单
  3. 与其他模式结合 - 常与 DFS/BFS 结合解决复杂问题
  4. 实际应用广泛 - 自动补全、拼写检查、IP 路由

Trie vs HashMap 对比

场景TrieHashMap
前缀匹配✅ O(m)❌ O(n×m)
精确查找✅ O(m)✅ O(m) 平均
公共前缀空间✅ 共享❌ 重复存储
字典序排序✅ 天然支持❌ 需额外排序
每节点内存❌ 数组/Map 开销✅ 最小

m = 单词长度，n = 单词数量

核心思想

共享前缀的魔力

单词: ["apple", "app", "apply", "apt", "bat"]

        (root)
       /      \
      a        b
      |        |
      p        a
     /|\       |
    p l t      t
    |  \
    l   y     ← "apply" 在此结束
    |
    e         ← "apple" 在此结束

带 ● 的节点是单词结束标记

核心洞察：共享前缀 “app” 的单词（apple、apply）从根节点到分叉点共享相同路径。

交互式 Trie 可视化

观察 insert、search 和 startsWith 操作的逐步执行过程：

Initializing...

实现模板

基于 Map（支持任意字符）

Loading...

基于数组（仅小写字母）

当输入仅包含小写字母 a-z 时，数组实现更快：

Loading...

如何选择实现方式？

方面Map/DictArray[26]
字符集任意 Unicode仅 a-z
内存稀疏，按需分配每节点 26 个指针
查找速度O(1) 哈希O(1) 直接索引
LeetCode更灵活略快

建议：面试中处理仅小写字母的问题时，数组实现因其简单性通常更受青睐。

详细示例

让我们追踪插入 “apple”、“app” 和 “apply” 的过程：

第一步：插入 “apple”

起始：空 Trie，只有根节点

插入 'a'：root → a（新建）
插入 'p'：a → p（新建）
插入 'p'：p → p（新建）
插入 'l'：p → l（新建）
插入 'e'：l → e（新建，标记为 END）

结果：
    (root)
       |
       a
       |
       p
       |
       p
       |
       l
       |
       e ●   ← isEnd = true

第二步：插入 “app”

遍历 'a'：存在，移动到 a
遍历 'p'：存在，移动到 p
遍历 'p'：存在，移动到 p → 标记为 END

结果：
    (root)
       |
       a
       |
       p
       |
       p ●   ← isEnd = true (app)
       |
       l
       |
       e ●   ← isEnd = true (apple)

第三步：插入 “apply”

遍历 'a'：存在
遍历 'p'：存在
遍历 'p'：存在
插入 'l'：存在，移动到 l
插入 'y'：l → y（新建，标记为 END）

结果：
    (root)
       |
       a
       |
       p
       |
       p ●
      /|
     l y ●   ← isEnd = true (apply)
     |
     e ●

时间和空间复杂度

操作时间空间
InsertO(m)最坏 O(m)
SearchO(m)O(1)
StartsWithO(m)O(1)

其中 m = 单词/前缀长度。

空间分析

对于 n 个平均长度为 m 的单词：

  • 最坏情况：O(n × m) - 无共享前缀
  • 最好情况：O(m) - 所有单词共享公共前缀
  • 典型情况：介于两者之间，取决于数据

LeetCode 208：实现 Trie (LC 208)

这是经典的 Trie 实现题。上面的模板可以直接解决。

// 使用示例
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // true
trie.search("app");     // false（未标记为结束）
trie.startsWith("app"); // true（前缀存在）
trie.insert("app");
trie.search("app");     // true（现在标记为结束了）

LeetCode 211：支持通配符的单词字典 (LC 211)

问题

设计一个数据结构，支持：

  • addWord(word) - 添加单词
  • search(word) - 返回单词是否存在（. 可匹配任意字母）

关键思路

遇到 . 时，必须递归尝试所有 26 个子节点。

Loading...

复杂度

  • addWord：O(m)
  • 无通配符搜索：O(m)
  • 有通配符搜索：O(26^k × m)，其中 k = . 字符的数量

LeetCode 212：单词搜索 II (LC 212)

问题

给定一个 m × n 字符网格和一个单词列表，找出所有可以通过相邻单元格顺序连接形成的单词。

为什么 Trie 在这里表现出色

朴素方法：对每个单词，从每个格子 DFS → O(n × m × words × 4^L)

Trie 方法：用单词构建 Trie，只 DFS 一次 → O(m × n × 4^L)

Trie 让我们能检查当前路径是否可能通向任何单词，实现早期剪枝。

Loading...

关键优化

  1. 在末尾节点存储完整单词 - 避免路径重建
  2. 移除已找到的单词 - 防止重复
  3. 剪枝空分支 - 移除没有剩余单词的节点

常见错误

1. 忘记标记结束

// ❌ 错误：从未标记单词结束
public void insert(String word) {
    Trie node = this;
    for (char c : word.toCharArray()) {
        int idx = c - 'a';
        if (node.children[idx] == null) {
            node.children[idx] = new Trie();
        }
        node = node.children[idx];
    }
    // 缺少：node.isEnd = true;
}

2. 混淆 search 和 startsWith

// search("app") 当 Trie 包含 "apple"
// 返回 FALSE - "app" 不是完整单词

// startsWith("app") 当 Trie 包含 "apple"  
// 返回 TRUE - "app" 是有效前缀

3. searchNode 返回值错误

// ❌ 错误：对前缀也返回 true
public boolean search(String word) {
    return searchNode(word) != null; // 还应该检查 isEnd！
}

// ✅ 正确
public boolean search(String word) {
    Trie node = searchNode(word);
    return node != null && node.isEnd;
}

面试技巧

如何解释 Trie

“Trie 是一棵树，每个节点代表一个字符。从根到任意节点的路径形成一个前缀。标记为 ‘end’ 的节点代表完整单词。这种结构允许 O(m) 的插入、搜索和前缀操作，其中 m 是单词长度。“

常见追问

问：如何找出所有具有给定前缀的单词？

导航到前缀末尾节点，然后 DFS 收集所有单词。

问：如何删除一个单词？

导航到末尾节点，取消 isEnd 标记。可选择剪枝空分支。

问：内存优化？

使用压缩 Trie（基数树），将单子节点链合并为一个带字符串的节点。

何时不使用 Trie

  1. 单次精确查找 - HashMap 更简单更快
  2. 单词集很小 - 开销不值得
  3. 非字符串键 - Trie 专为序列设计
  4. 内存受限 - 每个节点有 26+ 指针开销

相关 LeetCode 题目

题目难度核心概念
LC 208 - 实现 Trie中等基本实现
LC 211 - 添加与搜索单词中等通配符 + DFS
LC 212 - 单词搜索 II困难Trie + 网格 DFS
LC 677 - 键值映射中等带值的 Trie
LC 648 - 单词替换中等查找最短前缀
LC 1268 - 搜索推荐系统中等自动补全

总结

Trie 的适用场景：

  • ✅ 需要前缀操作
  • ✅ 多个字符串共享公共前缀
  • ✅ 需要字典序排序
  • ✅ 构建自动补全/拼写检查器

核心模板模式：

// 导航到节点
Trie node = this;
for (char c : word.toCharArray()) {
    int idx = c - 'a';
    if (node.children[idx] == null) {
        // 根据操作创建或返回 null
    }
    node = node.children[idx];
}
// 标记结束（insert）或检查结束（search）

记住：

  • search() = 节点存在 AND isEnd 为 true
  • startsWith() = 节点存在（不检查 isEnd）
  • 仅小写字母用 Array[26]，字符灵活用 Map
← 返回博客列表