Trie 前缀树 · Trie

一句话骨架：字符做边、节点存「是否到此为止是个完整单词」的多叉树。insert / search / startsWith 都是 O(L)（L 是单词长度），与字典里词条数无关。

极简实现

class Trie:
    def __init__(self):
        self.children = {}
        self.is_end = False

    def insert(self, word):
        node = self
        for ch in word:
            node = node.children.setdefault(ch, Trie())
        node.is_end = True

    def search(self, word):
        node = self._walk(word)
        return node is not None and node.is_end

    def startsWith(self, prefix):
        return self._walk(prefix) is not None

    def _walk(self, s):
        node = self
        for ch in s:
            if ch not in node.children: return None
            node = node.children[ch]
        return node

关卡 1 · 实现 Trie（前缀树）

学习目标

背下「children dict + is_end + setdefault」三件套；说清 search 与 startsWith 的差异。

#208实现 Trie（前缀树）中等

♥♥♥♥♥+0 XP🔥 0

0 / 12

📝 题目

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

输入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

输出[null, null, true, false, true, null, true]

约束

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

💡 思路：把每个字符当作一条边，节点记录「是否到此为止恰好是一个完整单词」。insert 沿路新建缺失的子节点；search 走完后还要校验 is_end；startsWith 只要走得通即可。三种操作都是 O(L)，与字典里词条数无关。

✅ 完整解法

时间 insert/search/startsWith 均为 O(L)，L 为字符串长度 · 空间 O(Σ N L)，N 为单词数、Σ 为字符集大小（最坏每条边都是新节点）

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1class Trie: 2    def __init__(self): 3        self.children = {}     # 当前节点的子节点：「字符」 -> 「子 Trie」 4        self.is_end = False    # 当前节点是否是某个完整单词的结尾 5  6    def insert(self, word: str) -> None: 7        node = self 8        for ch in word: 9            node = node.children.setdefault(ch, Trie())10        node.is_end = True11 12    def search(self, word: str) -> bool:13        node = self._walk(word)14        return node is not None and node.is_end15 16    def startsWith(self, prefix: str) -> bool:17        return self._walk(prefix) is not None18 19    def _walk(self, s: str):20        node = self21        for ch in s:22            if ch not in node.children:23                return None24            node = node.children[ch]25        return node

🐞 单步可视化

示例：insert("apple"), insert("app"), search("app"/"appl"), startsWith("appl")

代码L7

 1class Trie: 2    def __init__(self): 3        self.children = {}     # 当前节点的子节点：「字符」 -> 「子 Trie」 4        self.is_end = False    # 当前节点是否是某个完整单词的结尾 5  6    def insert(self, word: str) -> None: 7        node = self 8        for ch in word: 9            node = node.children.setdefault(ch, Trie())10        node.is_end = True11 12    def search(self, word: str) -> bool:13        node = self._walk(word)14        return node is not None and node.is_end15 16    def startsWith(self, prefix: str) -> bool:17        return self._walk(prefix) is not None18 19    def _walk(self, s: str):20        node = self21        for ch in s:22            if ch not in node.children:23                return None24            node = node.children[ch]25        return node

数据流

操作insert("apple")

·

1 / 37insert("apple")：从根开始，node=root

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

Trie 节点最常见的两种「子节点容器」实现是？

children 用 dict 还是 26 数组，主要权衡是？

node.children.setdefault(ch, Trie()) 等价于哪段手写代码？

 1class Trie: 2    def __init__(self): 3        self.children = {}     # 当前节点的子节点：「字符」 -> 「子 Trie」 4        self.is_end = False    # 当前节点是否是某个完整单词的结尾 5  6    def insert(self, word: str) -> None: 7        node = self 8        for ch in word: 9            node = node.children.setdefault(ch, Trie())10        node.is_end = True11 12    def search(self, word: str) -> bool:13        node = self._walk(word)14        return node is not None and node.is_end15 16    def startsWith(self, prefix: str) -> bool:17        return self._walk(prefix) is not None18 19    def _walk(self, s: str):20        node = self21        for ch in s:22            if ch not in node.children:23                return None24            node = node.children[ch]25        return node

为什么必须有 is_end 这个字段，而不能仅靠「节点存在」就判断 search？

 1class Trie: 2    def __init__(self): 3        self.children = {}     # 当前节点的子节点：「字符」 -> 「子 Trie」 4        self.is_end = False    # 当前节点是否是某个完整单词的结尾 5  6    def insert(self, word: str) -> None: 7        node = self 8        for ch in word: 9            node = node.children.setdefault(ch, Trie())10        node.is_end = True11 12    def search(self, word: str) -> bool:13        node = self._walk(word)14        return node is not None and node.is_end15 16    def startsWith(self, prefix: str) -> bool:17        return self._walk(prefix) is not None18 19    def _walk(self, s: str):20        node = self21        for ch in s:22            if ch not in node.children:23                return None24            node = node.children[ch]25        return node

search 与 startsWith 的差异在哪一行体现？

 1class Trie: 2    def __init__(self): 3        self.children = {}     # 当前节点的子节点：「字符」 -> 「子 Trie」 4        self.is_end = False    # 当前节点是否是某个完整单词的结尾 5  6    def insert(self, word: str) -> None: 7        node = self 8        for ch in word: 9            node = node.children.setdefault(ch, Trie())10        node.is_end = True11 12    def search(self, word: str) -> bool:13        node = self._walk(word)14        return node is not None and node.is_end15 16    def startsWith(self, prefix: str) -> bool:17        return self._walk(prefix) is not None18 19    def _walk(self, s: str):20        node = self21        for ch in s:22            if ch not in node.children:23                return None24            node = node.children[ch]25        return node

insert("apple") 之后内部结构最接近？

insert 一个长度为 L 的单词，时间复杂度是？

_walk 在中途遇到 ch not in node.children 时返回？

 1class Trie: 2    def __init__(self): 3        self.children = {}     # 当前节点的子节点：「字符」 -> 「子 Trie」 4        self.is_end = False    # 当前节点是否是某个完整单词的结尾 5  6    def insert(self, word: str) -> None: 7        node = self 8        for ch in word: 9            node = node.children.setdefault(ch, Trie())10        node.is_end = True11 12    def search(self, word: str) -> bool:13        node = self._walk(word)14        return node is not None and node.is_end15 16    def startsWith(self, prefix: str) -> bool:17        return self._walk(prefix) is not None18 19    def _walk(self, s: str):20        node = self21        for ch in s:22            if ch not in node.children:23                return None24            node = node.children[ch]25        return node

若把 self.children = {} 换成 self.children = [None]*26，怎么改 insert 才正确？

Trie 与「直接把所有前缀塞进 set」相比，主要优势是？

若题目要求支持「带通配符 . 的 search」（LeetCode 211），最自然的扩展是？

插入 N 个长度均为 L 的单词，最坏空间复杂度是？

关卡 2 · 单词搜索 II

学习目标

理解「灌 Trie 让多个单词共享前缀」为什么比逐题搜更快；掌握「占位 # + 出 dfs 还原」的网格回溯三段式。

#212单词搜索 II困难

♥♥♥♥♥+0 XP🔥 0

0 / 11

📝 题目

给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，返回所有二维网格上的单词。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中「相邻」单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例 1

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

输出["eat","oath"]

示例 2

输入board = [["a","b"],["c","d"]] words = ["abcb"]

输出[]

约束

• m == board.length, n == board[i].length
• 1 ≤ m, n ≤ 12
• 1 ≤ words.length ≤ 3 × 10⁴
• 1 ≤ words[i].length ≤ 10

💡 思路：一题一搜会重复扫格子。把所有 words 灌进 Trie，再从每个格子出发 DFS：当前字符必须在 Trie 当前节点的 children 里，否则立刻回头。命中 `$` 标记就把单词收入答案。「占位 # + 出 dfs 还原」是网格回溯三段式的标配。

✅ 完整解法

时间 O(m·n·4^L)，L 为最长单词长度（Trie 大幅剪枝实际远小于此） · 空间 O(总字符数) 用于 Trie，递归栈 O(L)

先把整段解法看懂，下面的选择题是对这段代码逐行的理解检验。

 1def findWords(board: list[list[str]], words: list[str]) -> list[str]: 2    # 1. 把所有 words 灌进 Trie，叶子节点存「完整单词」便于命中时直接收集 3    root = {} 4    for w in words: 5        node = root 6        for ch in w: 7            node = node.setdefault(ch, {}) 8        node['$'] = w   # 用 '$' 标记一个完整单词，值就是单词本身 9 10    m, n = len(board), len(board[0])11    res = []12 13    def dfs(i: int, j: int, node: dict) -> None:14        ch = board[i][j]15        if ch not in node:16            return17        nxt = node[ch]18        if '$' in nxt:19            res.append(nxt['$'])20            del nxt['$']        # 已收集，避免重复加入21        board[i][j] = '#'       # 占位，防止本路径再次走回来22        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):23            ni, nj = i+di, j+dj24            if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#':25                dfs(ni, nj, nxt)26        board[i][j] = ch        # 回溯还原27        # 可选剪枝：如果 nxt 已经空了，从父节点裁掉这条死路28        if not nxt:29            node.pop(ch, None)30 31    for i in range(m):32        for j in range(n):33            dfs(i, j, root)34    return res

🐞 单步可视化

示例：board=4×4, words=["oath","pea","eat","rain"]（应返回 ["eat","oath"]）

代码L2

 1def findWords(board: list[list[str]], words: list[str]) -> list[str]: 2    # 1. 把所有 words 灌进 Trie，叶子节点存「完整单词」便于命中时直接收集 3    root = {} 4    for w in words: 5        node = root 6        for ch in w: 7            node = node.setdefault(ch, {}) 8        node['$'] = w   # 用 '$' 标记一个完整单词，值就是单词本身 9 10    m, n = len(board), len(board[0])11    res = []12 13    def dfs(i: int, j: int, node: dict) -> None:14        ch = board[i][j]15        if ch not in node:16            return17        nxt = node[ch]18        if '$' in nxt:19            res.append(nxt['$'])20            del nxt['$']        # 已收集，避免重复加入21        board[i][j] = '#'       # 占位，防止本路径再次走回来22        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):23            ni, nj = i+di, j+dj24            if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#':25                dfs(ni, nj, nxt)26        board[i][j] = ch        # 回溯还原27        # 可选剪枝：如果 nxt 已经空了，从父节点裁掉这条死路28        if not nxt:29            node.pop(ch, None)30 31    for i in range(m):32        for j in range(n):33            dfs(i, j, root)34    return res

数据流

prefix(空)trie 路径(root)已收集 words[]动作建 trie

o

a

a

n

e

t

a

e

i

h

k

r

i

f

l

v

1 / 36阶段 1：把 words = ["oath","pea","eat","rain"] 建成 trie（root → 各分支）。下一步开始网格回溯。

速度 慢中快

🧠 理解检验

每题都对应解法的某一行或某个决策

为什么把所有 words 灌进 Trie，比逐个 word 调一遍 LC79 快？

在 Trie 末端用什么方式标记「这里恰好是某个完整单词」最好？

 1def findWords(board: list[list[str]], words: list[str]) -> list[str]: 2    # 1. 把所有 words 灌进 Trie，叶子节点存「完整单词」便于命中时直接收集 3    root = {} 4    for w in words: 5        node = root 6        for ch in w: 7            node = node.setdefault(ch, {}) 8        node['$'] = w   # 用 '$' 标记一个完整单词，值就是单词本身 9 10    m, n = len(board), len(board[0])11    res = []12 13    def dfs(i: int, j: int, node: dict) -> None:14        ch = board[i][j]15        if ch not in node:16            return17        nxt = node[ch]18        if '$' in nxt:19            res.append(nxt['$'])20            del nxt['$']        # 已收集，避免重复加入21        board[i][j] = '#'       # 占位，防止本路径再次走回来22        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):23            ni, nj = i+di, j+dj24            if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#':25                dfs(ni, nj, nxt)26        board[i][j] = ch        # 回溯还原27        # 可选剪枝：如果 nxt 已经空了，从父节点裁掉这条死路28        if not nxt:29            node.pop(ch, None)30 31    for i in range(m):32        for j in range(n):33            dfs(i, j, root)34    return res

收集到一个单词后，为什么要 del nxt["$"]？

 1def findWords(board: list[list[str]], words: list[str]) -> list[str]: 2    # 1. 把所有 words 灌进 Trie，叶子节点存「完整单词」便于命中时直接收集 3    root = {} 4    for w in words: 5        node = root 6        for ch in w: 7            node = node.setdefault(ch, {}) 8        node['$'] = w   # 用 '$' 标记一个完整单词，值就是单词本身 9 10    m, n = len(board), len(board[0])11    res = []12 13    def dfs(i: int, j: int, node: dict) -> None:14        ch = board[i][j]15        if ch not in node:16            return17        nxt = node[ch]18        if '$' in nxt:19            res.append(nxt['$'])20            del nxt['$']        # 已收集，避免重复加入21        board[i][j] = '#'       # 占位，防止本路径再次走回来22        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):23            ni, nj = i+di, j+dj24            if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#':25                dfs(ni, nj, nxt)26        board[i][j] = ch        # 回溯还原27        # 可选剪枝：如果 nxt 已经空了，从父节点裁掉这条死路28        if not nxt:29            node.pop(ch, None)30 31    for i in range(m):32        for j in range(n):33            dfs(i, j, root)34    return res

board[i][j] = "#" 这一步在做什么？

 1def findWords(board: list[list[str]], words: list[str]) -> list[str]: 2    # 1. 把所有 words 灌进 Trie，叶子节点存「完整单词」便于命中时直接收集 3    root = {} 4    for w in words: 5        node = root 6        for ch in w: 7            node = node.setdefault(ch, {}) 8        node['$'] = w   # 用 '$' 标记一个完整单词，值就是单词本身 9 10    m, n = len(board), len(board[0])11    res = []12 13    def dfs(i: int, j: int, node: dict) -> None:14        ch = board[i][j]15        if ch not in node:16            return17        nxt = node[ch]18        if '$' in nxt:19            res.append(nxt['$'])20            del nxt['$']        # 已收集，避免重复加入21        board[i][j] = '#'       # 占位，防止本路径再次走回来22        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):23            ni, nj = i+di, j+dj24            if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#':25                dfs(ni, nj, nxt)26        board[i][j] = ch        # 回溯还原27        # 可选剪枝：如果 nxt 已经空了，从父节点裁掉这条死路28        if not nxt:29            node.pop(ch, None)30 31    for i in range(m):32        for j in range(n):33            dfs(i, j, root)34    return res

在 dfs 出口处 board[i][j] = ch 这一句的作用？

 1def findWords(board: list[list[str]], words: list[str]) -> list[str]: 2    # 1. 把所有 words 灌进 Trie，叶子节点存「完整单词」便于命中时直接收集 3    root = {} 4    for w in words: 5        node = root 6        for ch in w: 7            node = node.setdefault(ch, {}) 8        node['$'] = w   # 用 '$' 标记一个完整单词，值就是单词本身 9 10    m, n = len(board), len(board[0])11    res = []12 13    def dfs(i: int, j: int, node: dict) -> None:14        ch = board[i][j]15        if ch not in node:16            return17        nxt = node[ch]18        if '$' in nxt:19            res.append(nxt['$'])20            del nxt['$']        # 已收集，避免重复加入21        board[i][j] = '#'       # 占位，防止本路径再次走回来22        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):23            ni, nj = i+di, j+dj24            if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#':25                dfs(ni, nj, nxt)26        board[i][j] = ch        # 回溯还原27        # 可选剪枝：如果 nxt 已经空了，从父节点裁掉这条死路28        if not nxt:29            node.pop(ch, None)30 31    for i in range(m):32        for j in range(n):33            dfs(i, j, root)34    return res

走完一个完整单词（即命中 $）后，是否需要 return（停止本路径）？

if not nxt: node.pop(ch, None) 这条剪枝意味着什么？

 1def findWords(board: list[list[str]], words: list[str]) -> list[str]: 2    # 1. 把所有 words 灌进 Trie，叶子节点存「完整单词」便于命中时直接收集 3    root = {} 4    for w in words: 5        node = root 6        for ch in w: 7            node = node.setdefault(ch, {}) 8        node['$'] = w   # 用 '$' 标记一个完整单词，值就是单词本身 9 10    m, n = len(board), len(board[0])11    res = []12 13    def dfs(i: int, j: int, node: dict) -> None:14        ch = board[i][j]15        if ch not in node:16            return17        nxt = node[ch]18        if '$' in nxt:19            res.append(nxt['$'])20            del nxt['$']        # 已收集，避免重复加入21        board[i][j] = '#'       # 占位，防止本路径再次走回来22        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):23            ni, nj = i+di, j+dj24            if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#':25                dfs(ni, nj, nxt)26        board[i][j] = ch        # 回溯还原27        # 可选剪枝：如果 nxt 已经空了，从父节点裁掉这条死路28        if not nxt:29            node.pop(ch, None)30 31    for i in range(m):32        for j in range(n):33            dfs(i, j, root)34    return res

检查 if ch not in node: return 放在 dfs 入口，对应 Trie 的什么思想？

 1def findWords(board: list[list[str]], words: list[str]) -> list[str]: 2    # 1. 把所有 words 灌进 Trie，叶子节点存「完整单词」便于命中时直接收集 3    root = {} 4    for w in words: 5        node = root 6        for ch in w: 7            node = node.setdefault(ch, {}) 8        node['$'] = w   # 用 '$' 标记一个完整单词，值就是单词本身 9 10    m, n = len(board), len(board[0])11    res = []12 13    def dfs(i: int, j: int, node: dict) -> None:14        ch = board[i][j]15        if ch not in node:16            return17        nxt = node[ch]18        if '$' in nxt:19            res.append(nxt['$'])20            del nxt['$']        # 已收集，避免重复加入21        board[i][j] = '#'       # 占位，防止本路径再次走回来22        for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):23            ni, nj = i+di, j+dj24            if 0 <= ni < m and 0 <= nj < n and board[ni][nj] != '#':25                dfs(ni, nj, nxt)26        board[i][j] = ch        # 回溯还原27        # 可选剪枝：如果 nxt 已经空了，从父节点裁掉这条死路28        if not nxt:29            node.pop(ch, None)30 31    for i in range(m):32        for j in range(n):33            dfs(i, j, root)34    return res

本题最坏时间复杂度的常见表达是？

Trie 用普通 class 写还是用嵌套 dict 写？

为什么用 board[i][j] = "#" 而不是 visited 二维数组？

同 pattern 索引（hot100 同类题）

题号	题名	难度	关键变形
211	添加与搜索单词	中等	search 支持通配符 . → 把 _walk 改写成 DFS，遇到 . 时枚举所有 children
648	单词替换	中等	把词根灌进 Trie，扫描时遇到第一个 is_end 就替换

hot100 几乎没有更多典型 Trie 题；理解 208/212 即覆盖面试中绝大多数 Trie 考点。

面试常踩

• is_end 字段不可省——区分「prefix 走得通」和「整词正好结束」，缺它就 search 与 startsWith 都同语义。
• dict vs 26 数组：dict 通用、稀疏更省；数组（小写英文场景）少一次哈希、缓存友好。两种都要会写。
• DFS 命中单词后不要 return——可能还有更长的单词以它为前缀（如 "app" 与 "apple"）。
• del nxt['$'] 防重复——多条路径都能拼出同一个单词时，必须命中后立刻抹标记。