自动补全、拼写检查、词频统计——字典树是字符串搜索的基石
字典树（Trie，又称前缀树）是一种树形数据结构，每条边代表一个字符，从根到某节点的路径对应一个字符串前缀。它特别适合处理字符串的前缀匹配问题，查找时间只与字符串长度有关，与集合大小无关。
class TrieNode:
def __init__(self):
self.children = {} # char → TrieNode
self.is_end = False # 是否单词结尾
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.is_end = True
def search(self, word: str) -> bool:
node = self._find(word)
return node is not None and node.is_end
def startsWith(self, prefix: str) -> bool:
return self._find(prefix) is not None
def _find(self, prefix: str):
"""沿前缀走，返回终点节点或None"""
node = self.root
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return nodedict 做 children 比 List[Optional[TrieNode]]（26个位置）更省空间，因为不需要为不存在的字符分配空间。如果只处理小写字母，也可以用 26 长度的列表，速度略快。题目描述：实现 Trie 类，支持 insert、search、startsWith 三个操作。
class Trie:
def __init__(self):
self.children = {}
self.is_end = False
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.is_end = True
def search(self, word: str) -> bool:
node = self._find(word)
return node is not None and node.is_end
def startsWith(self, prefix: str) -> bool:
return self._find(prefix) is not None
def _find(self, prefix: str):
node = self
for ch in prefix:
if ch not in node.children:
return None
node = node.children[ch]
return nodeinsert 时间：O(L)，search 时间：O(L)，startsWith 时间：O(L)
空间复杂度：O(N×L)，N为单词数，L为平均长度（公共前缀共享后更少）
题目描述：设计一个数据结构，支持添加单词和搜索单词。搜索时，. 可以匹配任意一个字母。
.，需要尝试所有子节点，用递归（DFS）处理。遇到普通字符，走对应的子节点；遇到 .，遍历所有子节点递归搜索。
class WordDictionary:
def __init__(self):
self.children = {}
self.is_end = False
def addWord(self, word: str) -> None:
node = self
for ch in word:
if ch not in node.children:
node.children[ch] = WordDictionary()
node = node.children[ch]
node.is_end = True
def search(self, word: str) -> bool:
return self._search(word, 0)
def _search(self, word: str, idx: int) -> bool:
if idx == len(word):
return self.is_end
ch = word[idx]
if ch == '.':
# 通配符：尝试所有子节点
return any(
child._search(word, idx + 1)
for child in self.children.values()
)
if ch not in self.children:
return False
return self.children[ch]._search(word, idx + 1)addWord：O(L)
search 最坏：O(26^L)（全通配符），但实际远好于此
. 的处理是考点。关键是不要把 . 当特殊字符插入 Trie，只在搜索时处理。面试官可能会问"如果通配符是 * 匹配零或多个字符呢？"那需要更复杂的回溯。题目描述：给定 m×n 字符网格和单词列表，找出所有同时在网格和列表中出现的单词。单词由相邻格子（上下左右）的字母组成，同一格子不能重复使用。
class Solution:
def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
# 建 Trie，节点存完整单词
class TrieNode:
def __init__(self):
self.children = {}
self.word = None # 存完整单词（非None表示是单词结尾）
root = TrieNode()
for word in words:
node = root
for ch in word:
if ch not in node.children:
node.children[ch] = TrieNode()
node = node.children[ch]
node.word = word
rows, cols = len(board), len(board[0])
result = []
def dfs(r, c, node):
ch = board[r][c]
if ch not in node.children:
return
child = node.children[ch]
if child.word:
result.append(child.word)
child.word = None # 避免重复添加
board[r][c] = '#' # 标记已访问
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 and board[nr][nc] != '#':
dfs(nr, nc, child)
board[r][c] = ch # 回溯
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return result时间复杂度：O(m×n×4×3^(L-1))，L为最长单词长度
空间复杂度：O(总字符数)，Trie 空间
child.word = None，这样同一个单词不会被重复添加，而且如果该节点没有子节点，后续路径也不会再走到这里，起到剪枝效果。在 TrieNode 中增加 count 字段，插入时路径上每个节点 count+1，可以统计每个前缀出现次数。
class TrieNode:
def __init__(self):
self.children = {}
self.count = 0 # 经过此节点的单词数
self.is_end = 0 # 以此节点结尾的单词数
# 插入时: node.count += 1, 最后 node.is_end += 1
# 查前缀频率: 沿前缀走到节点, 返回 node.count将数字的二进制表示插入 01-Trie，可以在 O(32) 时间内找到与目标数异或值最大的数。这是 LC 421 和 LC 1707 的核心解法。
# 01-Trie: 每个节点只有 0 和 1 两个子节点
class BitTrie:
def __init__(self):
self.children = [None, None] # [bit0, bit1]
# 查最大异或: 尽量走相反位
# 如果目标位是0, 优先走1; 如果目标位是1, 优先走0Trie 处理前缀，后缀自动机处理子串。如果问题涉及子串匹配而非前缀匹配，Trie 可能不是最佳选择。
. 递归搜索所有子节点