30 秒速览

  • 结构：根到节点的路径表示一个字符串
  • 核心操作：insert、search、startsWith
  • 时间复杂度：O(L)，L 是字符串长度
  • 典型应用：自动补全、拼写检查、词频统计

一、直觉建立

什么是字典树？

想象你要查字典里 “apple” 这个词：

  1. 先找 ‘a’ 开头的部分
  2. 在 ‘a’ 下面找 ‘ap’
  3. 继续 ‘app’ → ‘appl’ → ‘apple’

字典树就是把这种查找方式结构化：

        root
       /|\
      a b c
      |   |
      p   a
      |   |
      p   t
     /|\  |
    l e   ...
   /
  e (end)

为什么用字典树？

操作哈希表字典树
精确查找O(1)O(L)
前缀匹配O(N×L)O(L)
按字典序遍历需排序O(N×L)

字典树在前缀相关操作上有绝对优势。

二、字典树结构

节点定义

class TrieNode:
    def __init__(self):
        self.children = {}  # 字符 → 子节点
        self.is_end = False  # 是否是单词结尾

Trie 类

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        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) -> 'TrieNode':
        node = self.root
        for c in prefix:
            if c not in node.children:
                return None
            node = node.children[c]
        return node

时间复杂度：所有操作 O(L)，L 是字符串长度 空间复杂度：O(N×L)，N 是单词数，L 是平均长度

三、典型例题

例题 1：LC 208. 实现 Trie（前缀树）

已在上面讲解。

例题 2：LC 211. 添加与搜索单词

题目：支持 ‘.’ 通配符搜索，’.’ 可以匹配任意字符。

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True

    def search(self, word: str) -> bool:
        return self._search_helper(word, 0, self.root)

    def _search_helper(self, word: str, index: int, node: TrieNode) -> bool:
        if index == len(word):
            return node.is_end

        c = word[index]

        if c == '.':
            # 尝试所有子节点
            for child in node.children.values():
                if self._search_helper(word, index + 1, child):
                    return True
            return False
        else:
            if c not in node.children:
                return False
            return self._search_helper(word, index + 1, node.children[c])

复杂度：search 最坏 O(26^L)，L 是单词长度

例题 3：LC 212. 单词搜索 II

题目：在二维字符网格中找出所有单词。

示例：

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]],
      words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

思路

把单词建成字典树，在网格中 DFS 时，沿着字典树路径走。

class Solution:
    def findWords(self, board: list[list[str]], words: list[str]) -> list[str]:
        # 构建字典树
        root = {}
        for word in words:
            node = root
            for c in word:
                if c not in node:
                    node[c] = {}
                node = node[c]
            node['#'] = word  # 用特殊标记存完整单词

        m, n = len(board), len(board[0])
        result = []

        def dfs(i, j, node):
            c = board[i][j]

            if c not in node:
                return

            next_node = node[c]

            # 找到单词
            if '#' in next_node:
                result.append(next_node['#'])
                del next_node['#']  # 避免重复

            # 标记已访问
            board[i][j] = '*'

            for di, dj in [(1,0), (-1,0), (0,1), (0,-1)]:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n:
                    dfs(ni, nj, next_node)

            # 恢复
            board[i][j] = c

        for i in range(m):
            for j in range(n):
                dfs(i, j, root)

        return result

复杂度：时间 O(M×N×4^L)，L 是最长单词长度

例题 4：LC 720. 词典中最长的单词

题目：找最长的单词，要求它的每个前缀都在词典中。

思路

按长度排序，逐个检查前缀是否都存在。

def longestWord(words: list[str]) -> str:
    word_set = set(words)
    words.sort(key=lambda x: (-len(x), x))  # 长度降序，字典序升序

    for word in words:
        # 检查所有前缀
        valid = True
        for i in range(1, len(word)):
            if word[:i] not in word_set:
                valid = False
                break
        if valid:
            return word

    return ""

Trie 解法

def longestWord(words: list[str]) -> str:
    # 构建字典树
    root = TrieNode()
    for word in words:
        node = root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True

    result = ""

    def dfs(node, path):
        nonlocal result
        for c, child in sorted(node.children.items()):
            if child.is_end:  # 只走完整单词路径
                dfs(child, path + c)

        if len(path) > len(result) or (len(path) == len(result) and path < result):
            result = path

    dfs(root, "")
    return result

例题 5：LC 648. 单词替换

题目：用词根替换句子中的单词。

示例：

输入：dictionary = ["cat","bat","rat"], sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"

def replaceWords(dictionary: list[str], sentence: str) -> str:
    # 构建字典树
    root = {}
    for word in dictionary:
        node = root
        for c in word:
            if c not in node:
                node[c] = {}
            node = node[c]
        node['#'] = True

    def find_root(word: str) -> str:
        node = root
        for i, c in enumerate(word):
            if '#' in node:
                return word[:i]
            if c not in node:
                break
            node = node[c]
        return word

    return ' '.join(find_root(w) for w in sentence.split())

四、Trie 变体

01 字典树（位运算）

用于处理二进制数的异或问题。

class BitTrie:
    def __init__(self, max_bits=31):
        self.root = {}
        self.max_bits = max_bits

    def insert(self, num: int):
        node = self.root
        for i in range(self.max_bits, -1, -1):
            bit = (num >> i) & 1
            if bit not in node:
                node[bit] = {}
            node = node[bit]

    def find_max_xor(self, num: int) -> int:
        node = self.root
        xor_val = 0

        for i in range(self.max_bits, -1, -1):
            bit = (num >> i) & 1
            want = 1 - bit  # 希望相反的位

            if want in node:
                xor_val |= (1 << i)
                node = node[want]
            else:
                node = node[bit]

        return xor_val

压缩字典树（Radix Tree）

合并只有一个子节点的链，节省空间。

五、常见错误与陷阱

错误 1：忘记 is_end 标记

# 错误：只插入，没标记结尾
def insert(self, word):
    node = self.root
    for c in word:
        if c not in node.children:
            node.children[c] = TrieNode()
        node = node.children[c]
    # 忘记 node.is_end = True

# search 会误判 "app" 为 "apple" 的存在

错误 2：search vs startsWith

# search：必须是完整单词
return node is not None and node.is_end

# startsWith：只要前缀存在
return node is not None

错误 3：DFS 时状态恢复

# 在网格 DFS 中，记得恢复状态
board[i][j] = '*'  # 标记
dfs(...)
board[i][j] = c    # 恢复！

错误 4：通配符搜索遗漏分支

# '.' 要尝试所有子节点
if c == '.':
    for child in node.children.values():
        if dfs(child, index + 1):
            return True
    return False

六、复盘清单

触发信号

  • 前缀匹配
  • 大量字符串查找
  • 字符串集合操作
  • 自动补全/拼写检查

实现检查

  • 节点结构正确
  • is_end 标记
  • search vs startsWith 区分
  • 递归时状态正确

变体应用

  • 通配符搜索
  • 网格搜索
  • 位 Trie（异或问题）

七、题目清单

基础题

题号题目难度考点
208实现 TrieMedium基本操作
720最长单词Easy前缀检查
648单词替换Medium前缀匹配

进阶题

题号题目难度考点
211添加与搜索单词Medium通配符
212单词搜索 IIHardTrie + DFS
421数组最大异或Medium01 字典树
677键值映射Medium带计数