字典树（Trie），又称前缀树，让字符串检索达到 O(m) 时间复杂度，m 为字符串长度。
什么是字典树？
字典树是一种树形数据结构，用于高效存储和检索字符串集合。核心思想：共享前缀，节省空间。
示例：["apple", "app", "apply", "ban", "band"]
root
/ \
a b
/ \ \
p p a
/ \ \ |
p l l n
| | | |
l y y d
| （apple, app, apply, ban, band）
所有以 “app” 开头的单词共享同一条路径，大大节省存储空间。
字典树的核心操作
1. 基本结构
class TrieNode:
def __init__(self):
self.children = {} # 子节点映射 {char: TrieNode}
self.is_end = False # 是否是单词结尾
self.word = None # 结尾的完整单词（可选）
class Trie:
def __init__(self):
self.root = TrieNode()
# 插入
def insert(self, word: str):
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
node.word = word
# 搜索
def search(self, word: str) -> bool:
node = self._find_node(word)
return node is not None and node.is_end
# 前缀匹配
def startsWith(self, prefix: str) -> bool:
return self._find_node(prefix) is not None
def _find_node(self, prefix: str):
node = self.root
for char in prefix:
if char not in node.children:
return None
node = node.children[char]
return node
2. 时间复杂度
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 插入 | O(m) | O(m) |
| 搜索 | O(m) | O(1) |
| 前缀匹配 | O(m) | O(1) |
m = 字符串长度
优势：相比哈希表，字典树可以高效处理前缀查询。
LeetCode 实战
题目 1：实现 Trie（前缀树）
LeetCode 208 - 实现一个 Trie，支持 insert、search、startsWith 操作。
class Trie:
def __init__(self):
self.root = {}
def insert(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node:
node[ch] = {}
node = node[ch]
node['#'] = True # 标记单词结尾
def search(self, word: str) -> bool:
node = self._traverse(word)
return node is not None and '#' in node
def startsWith(self, prefix: str) -> bool:
return self._traverse(prefix) is not None
def _traverse(self, prefix: str):
node = self.root
for ch in prefix:
if ch not in node:
return None
node = node[ch]
return node
题目 2：单词搜索 II
LeetCode 212 - 在二维字符网格中找出所有存在于字典里的单词。
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
# 构建 Trie
trie = {}
for word in words:
node = trie
for ch in word:
node = node.setdefault(ch, {})
node['#'] = word
result = []
rows, cols = len(board), len(board[0])
def dfs(r, c, node):
ch = board[r][c]
if ch not in node:
return
next_node = node[ch]
# 找到完整单词
if '#' in next_node:
result.append(next_node['#'])
del next_node['#'] # 避免重复
# 标记已访问
board[r][c] = '#'
# 四个方向 DFS
for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
dfs(nr, nc, next_node)
board[r][c] = ch # 回溯
# 剪枝：叶节点可删除
if not next_node:
del node[ch]
for r in range(rows):
for c in range(cols):
if board[r][c] in trie:
dfs(r, c, trie)
return result
优化要点：
- 用字典而非固定数组，更省空间
- 找到单词后删除叶节点，实现剪枝
- 回溯恢复字符状态
前缀树的应用场景
1. 自动补全 / 输入提示
搜索引擎、IDE 代码补全：
# 模拟搜索框前缀匹配
def autocomplete(trie, prefix, top_k=5):
node = trie._find_node(prefix)
if not node:
return []
# DFS 收集所有以 prefix 开头的单词
results = []
def dfs(n, path):
if len(results) >= top_k:
return
if '#' in n:
results.append(path)
for ch, child in n.items():
if ch != '#':
dfs(child, path + ch)
dfs(node, prefix)
return results
2. IP 路由最长前缀匹配
网络路由表使用 Trie 进行最长前缀匹配。
3. 字符串排序
字典树的中序遍历即为按字典序排列的字符串序列。
4. 敏感词过滤
将敏感词库构建为 Trie，扫描文本时 O(n) 时间复杂度完成匹配。
字典树的变体
1. 压缩字典树（Compressed Trie）
将单字符节点压缩为字符串节点，减少节点数量：
压缩前：a → b → c → d
压缩后：abcd（单个节点存储字符串）
2. 后缀树（Suffix Tree）
存储字符串所有后缀，用于子串查询、模式匹配等问题。
3. 双数组字典树（Double-Array Trie）
用两个数组实现，兼顾速度和空间，是工业级词典分词的核心结构。
💡 小结
字典树的核心价值：
| 特性 | 说明 |
|---|---|
| 前缀共享 | 节省空间，适合字符串集合 |
| O(m) 查找 | m = 字符串长度，与规模无关 |
| 天然支持前缀查询 | 哈希表做不到 |
| 可扩展性强 | 轻松添加删除、统计词频 |
适用场景：前缀匹配、自动补全、敏感词过滤、词典分词。
面试高频：LeetCode 208（实现 Trie）、212（单词搜索 II）、820（单词压缩）。
相关阅读：并查集——城市连接问题