208. 实现 Trie (前缀树)

题目链接（中等）

题目描述

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。

请你实现 Trie 类：

• Trie()：初始化前缀树对象。
• void insert(String word)：向前缀树中插入字符串 word。
• boolean search(String word)：如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false。
• boolean startsWith(String prefix)：如果之前已经插入的字符串 word 的前缀之一为 prefix，返回 true；否则，返回 false。

数据范围：

• 1 <= word.length, prefix.length <= 2000
• word 和 prefix 仅由小写英文字母组成
• insert、search 和 startsWith 调用次数总计不超过 3 * 10^4 次

示例

输入：

["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]

输出：

[null, null, true, false, true, null, true]

解释：

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

核心思路

Trie（前缀树 / 字典树） 是一棵有根树，用于存储字符串集合，每个节点代表一个字符，从根到某个节点的路径构成一个前缀。

每个节点包含两个字段：

• children：指向子节点的指针数组。对本题而言，长度 26（小写字母），children[0] 对应 'a'，children[1] 对应 'b'，以此类推；
• isEnd：布尔值，标记「从根到当前节点的路径是否构成一个完整的单词」。

Trie 的优势：

• 插入和查询都是 $O(L)$（$L$ 为字符串长度），与集合大小无关；
• 天然支持「前缀查询」，这是哈希表做不到的。

Trie 的直觉图：

插入 ["apple", "app"] 后：

root
 └─ a
     └─ p
         └─ p
             ├─ l       ← "app" 在此结束（isEnd=True）
             │   └─ e   ← "apple" 在此结束（isEnd=True）
             └─ ...     (其他子节点)

app 和 apple 共享前缀路径 a → p → p，节省空间。

---

方法一：数组存储子节点

思路及解法

用长度 26 的数组存储每个节点的子节点，下标 = ord(ch) - ord('a')。

insert(word)：

1. 从根节点出发，对 word 的每个字符：
   • 如果对应子节点不存在，新建一个；
   • 移动到子节点；
2. 处理完所有字符后，把最后一个节点的 isEnd 设为 True。

searchPrefix(prefix)（辅助函数）：

1. 从根出发，对 prefix 的每个字符：
   • 如果对应子节点不存在，返回 None；
   • 否则移动到子节点；
2. 处理完所有字符后，返回最后一个节点。

search(word)：

• 先调用 searchPrefix(word)，若返回 None 则不存在；
• 否则，还需要检查返回节点的 isEnd 是否为 True（因为 word 可能只是某个更长单词的前缀）。

startsWith(prefix)：

• 只需 searchPrefix(prefix) is not None 即可，不需要检查 isEnd。

代码

class Trie:
    def __init__(self):
        self.children = [None] * 26      # 26 个小写字母
        self.isEnd = False               # 标记是否为单词结尾

    def searchPrefix(self, prefix: str) -> "Trie":
        """返回 prefix 对应的最后一个节点，不存在则返回 None"""
        node = self
        for ch in prefix:
            idx = ord(ch) - ord('a')
            if not node.children[idx]:
                return None
            node = node.children[idx]
        return node

    def insert(self, word: str) -> None:
        node = self
        for ch in word:
            idx = ord(ch) - ord('a')
            if not node.children[idx]:
                node.children[idx] = Trie()
            node = node.children[idx]
        node.isEnd = True

    def search(self, word: str) -> bool:
        node = self.searchPrefix(word)
        return node is not None and node.isEnd

    def startsWith(self, prefix: str) -> bool:
        return self.searchPrefix(prefix) is not None

复杂度分析

• 时间复杂度：初始化 $O(1)$，其余操作 $O(|S|)$，$|S|$ 为插入或查询的字符串长度。
• 空间复杂度：$O(|T| \cdot \Sigma)$，$|T|$ 为所有插入字符串的长度之和，$\Sigma = 26$ 为字符集大小。

---

方法二：哈希表存储子节点

思路及解法

如果字符集不固定（比如包含 Unicode），用数组就不好处理。可以用哈希表（Python 中的 dict）存储子节点：

• children：dict，key 是字符，value 是对应子节点；
• 其他逻辑和方法一完全一致。

优点：支持任意字符集，节省稀疏节点的空间（只存实际用到的子节点）。 缺点：字典操作有常数开销，比数组稍慢。

代码

class Trie:
    def __init__(self):
        self.children = {}               # 字符 -> Trie 节点
        self.isEnd = False

    def searchPrefix(self, prefix: str) -> "Trie":
        node = self
        for ch in prefix:
            if ch not in node.children:
                return None
            node = node.children[ch]
        return node

    def insert(self, word: str) -> None:
        node = self
        for ch in word:
            if ch not in node.children:
                node.children[ch] = Trie()
            node = node.children[ch]
        node.isEnd = True

    def search(self, word: str) -> bool:
        node = self.searchPrefix(word)
        return node is not None and node.isEnd

    def startsWith(self, prefix: str) -> bool:
        return self.searchPrefix(prefix) is not None

复杂度分析

• 时间复杂度：同方法一，均为 $O(|S|)$。
• 空间复杂度：$O(|T|)$，只存储实际存在的边，比数组版本更省。

---

两种方法对比

方法	字符集	查询速度	空间	特点
数组	固定（26 字母）	快	$O(|T| \cdot 26)$	下标访问 $O(1)$，无哈希开销
哈希表	任意	稍慢	$O(|T|)$	支持任意字符，省稀疏空间

推荐：

• 面试：方法一（数组），符合题目「小写字母」的约定，代码更紧凑，查询更快；
• 通用场景：方法二（哈希表），字符集不限，节省空间。

---

关键细节

1. search 和 startsWith 的区别

• search：必须匹配完整单词，所以除了找到路径，还要检查 node.isEnd；
• startsWith：只需匹配前缀，找到路径即可，不需要检查 isEnd。

举例：插入 "apple" 后：

查询	结果	原因
search("apple")	True	完整单词，isEnd = True
search("app")	False	路径存在，但 "app" 未标记为单词结尾
startsWith("app")	True	前缀存在

2. 为什么要复用 searchPrefix

search 和 startsWith 的查找过程完全相同，只是最后判断 isEnd 与否。抽出一个 searchPrefix 函数可以让代码更简洁，也避免重复。

3. isEnd 为什么不能省

如果所有插入单词的末节点都不标记 isEnd，search("app") 就会误判为 True（因为路径存在）。isEnd 用来区分「路径存在」和「完整单词存在」。

4. 为什么不存完整单词

Trie 只存字符，不存完整单词。这样能共享相同前缀，节省空间。查询时按字符逐层下探，路径就是前缀。

5. Trie 的典型应用

• 自动补全：给定前缀，返回所有匹配的单词；
• 拼写检查：判断单词是否在字典中；
• IP 路由：最长前缀匹配；
• 单词搜索 II（LC 212）：Trie + DFS 剪枝；
• 敏感词过滤：多模式串匹配。

---

总结

• Trie 的核心结构：每个节点 children（子节点）+ isEnd（单词结束标记）；
• 操作都是 $O(L)$，$L$ 是字符串长度：
  • insert：逐字符下探，不存在则新建；
  • search / startsWith：逐字符下探，找不到就失败；
• 区分 search 和 startsWith：前者还要检查 isEnd；
• 两种子节点实现：数组（固定字符集）vs 哈希表（任意字符集）；
• 记忆口诀：「Trie = 前缀共享的树 + 单词结束标记」。

相关题目

• LC 211. 添加与搜索单词（支持 . 通配符，需要 DFS）
• LC 212. 单词搜索 II（Trie + 网格 DFS）
• LC 648. 单词替换（前缀替换）
• LC 677. 键值映射（Trie 上存值）
• LC 745. 前缀和后缀搜索