字典树（Trie）

Trie 这个数据结构最直观的类比就是手机的"打字预测"——打到 "ap" 弹出 apple / app / application，根本不用每次都把整本字典翻一遍。它的全部秘密就一句话：把一组字符串压成一棵树，每个字符是一条边，相同前缀只占一条路径。

它能压扁哪一族题？前缀匹配、通配符查询、最短前缀替换、字典里的网格 DFS、整数异或最大值……这些题用 HashSet / 排序都能勉强写，但要么 TLE、要么代码丑得不行。Trie 把它们全部统一到同一套"沿着路径走一遍"的模板里。

本章按"基础 → 通配符 → 应用 → 01-Trie"四段式推进。掌握 Trie 三件套 insert / search / startsWith，剩下的题不过是把"末节点 is_end"换成"末节点存 word / 存 weight / 存出现次数"——换汤不换药。

1. 核心原理

Trie（读 "try"），又称前缀树（Prefix Tree），是一种以字符串集合为内容的多叉树。约定：根节点不存字符；从根到某节点路径上的字符依次拼接，就是这个节点所代表的前缀；节点上一个布尔标记 is_end 表示"该前缀本身也是一个被插入过的完整词"。同一前缀在树中只占一条路径，因此 n 个串长度上界为 L 的字典最多占用 O(n · L) 个节点。

针对字符串字典的核心三件套——insert(word) / search(word) / startsWith(prefix)——Trie 统一为"从根沿字符走 L 步"的同一形式，单次操作 O(L)，与字典已有词数 n 无关。

暴力为什么不行

朴素做法是把所有词丢进 HashSet<String>。insert 与等值 search 平均 O(L)，但 startsWith 没法直接回答：HashSet 只支持等值查询，要枚举前缀就得对集合中每个词逐个 startsWith 比对，最坏 O(n · L)。LC 208 调用上限 3 × 10⁴，遇到极端样例就 TLE。

空间也亏。"apple"、"app"、"application" 在 HashSet 里独立存三份，公共前缀 "app" 被复制三次：

HashSet 视角：               Trie 视角：
"apple"        ─┐                root
"app"          ─┼─ 各存一份       │ a-p-p (is_end=True)
"application"  ─┘                ├── l-e (is_end=True)
                                 └── l-i-c-a-t-i-o-n (is_end=True)

我们要的数据结构同时满足：① 三件套全 O(L)；② 公共前缀只存一次。这两条直接逼出 Trie。

核心洞察：把字符串折叠成路径

把字符串看成"从根出发，每个字符走一条边"的路径。共享相同前缀的词自然走相同的开头一段，分叉点之后各自延伸：

插入 "apple"、"app"、"application" 后的 Trie：

           (root)
             │ a
             ▼
             p
             │ p
             ▼
             p  ← is_end=True（"app" 在此结束）
        ┌────┴────┐
      l │         │ l
        ▼         ▼
        e         i
   is_end=True    │ c-a-t-i-o-n
   ("apple")      ▼  ... 末节点 is_end=True ("application")

is_end 把两个相似询问彻底分开：

• search("app")：走到 a→p→p 后看末节点 is_end 是否为 True
• startsWith("app")：走到 a→p→p 即返回 True，不管末节点的 is_end

节点的两个字段

一个 Trie 节点只需要两件东西：

1. children：子节点引用。小写字母字典固定 26 路，children[c - 'a'] 指向"沿字符 c 走的下一个节点"；字符集大或稀疏时换成 dict<char, Node>。
2. is_end：布尔值，标记"根到此节点的路径"是不是一个被完整插入过的词。

Node {
    children: array[26]  // 或 dict
    is_end:   bool
}

三个操作的统一骨架是"从 root 出发顺着字符串走 L 步"：

三件套均为 O(L)，与字典已有词数无关——这正是 Trie 相对 HashSet 的关键胜负手：startsWith 不再遍历字典。

数组 children 还是 dict children

数组版（固定 26 / 256 槽）：
  Node { children: [Node?; 26], is_end: bool }
  优点：下标访问 O(1)、缓存友好、常数小
  缺点：每节点固定 26 个槽（多为 None），稀疏时浪费

哈希版（dict<char, Node>）：
  Node { children: Map<char, Node>, is_end: bool }
  优点：稀疏字符集（Unicode、混合大小写）省空间
  缺点：每次访问要 hash，常数更大

工程取舍：

• 字符集为小写英文字母（LC 208 / 211 / 648 这一族）—— 用数组，速度更快
• 字符集大或不固定（Unicode、域名、IP 段）—— 用 dict
• 内存极端紧张 —— 双数组 Trie / 压缩 Trie / Radix Tree，常见面试不涉及

01-Trie：字符集换成 2 的 Trie

把整数看成 32 位（或 64 位）二进制串、每个 bit 视为一个字符——这就是 01-Trie。每个节点最多 2 个 child，深度固定 32 层，常用于"一对数的最大异或"这一族（LC 421）。

插入 3 (二进制 011) 与 5 (二进制 101) 到 3-bit 01-Trie：

       (root)
        ├─ 0 ───┐
        │       └─ 1 ─── 1   (3 = 011)
        └─ 1 ───┐
                └─ 0 ─── 1   (5 = 101)

骨架与字符串 Trie 完全一致，只是字符集从 26 缩到 2、深度由变长变成固定。本章主线先把字符串 Trie 跑通，01-Trie 留到 §6.3 LC 421 展开。

空间复杂度

每个节点固定占 26 × 指针（数组版）。n 个长度上界 L 的词，最坏（两两完全不共享前缀）需要 O(n · L) 个节点、O(n · L · 26) 个指针格。共享前缀越多，节省越显著——这正是 Trie 相对 HashSet 的空间收益来源。

2. 通用模板

下面给字符串 Trie 的最小骨架（数组 children、字符集小写英文字母）。三个 Tab 接口完全一致：insert(word) / search(word) / startsWith(prefix)，配合一个内部帮手 _walk 复用"沿字符串走 L 步"的公共部分。

class Trie:
    def __init__(self):
        self.children: list[Trie | None] = [None] * 26   # 26 路数组
        self.is_end: bool = False                        # 该节点是否为某个完整词的末尾

    def insert(self, word: str) -> None:
        node = self
        for ch in word:
            idx = ord(ch) - ord('a')
            if node.children[idx] is None:               # 路径上缺节点就新建
                node.children[idx] = Trie()
            node = node.children[idx]
        node.is_end = True                               # 末节点打标

    def search(self, word: str) -> bool:
        node = self._walk(word)                          # 复用公共"沿路径走"
        return node is not None and node.is_end          # 必须 is_end 才算命中

    def startsWith(self, prefix: str) -> bool:
        return self._walk(prefix) is not None            # 末节点是否存在即可

    def _walk(self, s: str) -> "Trie | None":
        node = self
        for ch in s:
            idx = ord(ch) - ord('a')
            if node.children[idx] is None:
                return None
            node = node.children[idx]
        return node

class Trie {
    private final Trie[] children = new Trie[26];        // 26 路数组
    private boolean isEnd = false;                       // 是否为完整词末尾

    public void insert(String word) {
        Trie node = this;
        for (char ch : word.toCharArray()) {
            int idx = ch - 'a';
            if (node.children[idx] == null) {            // 路径缺节点就新建
                node.children[idx] = new Trie();
            }
            node = node.children[idx];
        }
        node.isEnd = true;                               // 末节点打标
    }

    public boolean search(String word) {
        Trie node = walk(word);
        return node != null && node.isEnd;               // 必须 isEnd 为 true
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null;                     // 末节点存在即可
    }

    private Trie walk(String s) {                        // 复用沿路径走 L 步
        Trie node = this;
        for (char ch : s.toCharArray()) {
            int idx = ch - 'a';
            if (node.children[idx] == null) return null;
            node = node.children[idx];
        }
        return node;
    }
}

class Trie {
    array<Trie*, 26> children{};                         // 26 路数组（默认 nullptr）
    bool isEnd = false;                                  // 是否为完整词末尾

public:
    Trie() = default;

    void insert(const string& word) {
        Trie* node = this;
        for (char ch : word) {
            int idx = ch - 'a';
            if (node->children[idx] == nullptr) {        // 路径缺节点就新建
                node->children[idx] = new Trie();
            }
            node = node->children[idx];
        }
        node->isEnd = true;                              // 末节点打标
    }

    bool search(const string& word) {
        Trie* node = walk(word);
        return node != nullptr && node->isEnd;           // 必须 isEnd 为 true
    }

    bool startsWith(const string& prefix) {
        return walk(prefix) != nullptr;                  // 末节点存在即可
    }

private:
    Trie* walk(const string& s) {                        // 复用沿路径走 L 步
        Trie* node = this;
        for (char ch : s) {
            int idx = ch - 'a';
            if (node->children[idx] == nullptr) return nullptr;
            node = node->children[idx];
        }
        return node;
    }
};

骨架几点要说明：

• 三件套都靠同一份 _walk / walk：search 和 startsWith 共用沿路径走逻辑，只在末节点的判定上分叉——前者要求 is_end == True、后者只要末节点存在。统一抽出帮手能避免两边写漏。
• 复杂度：insert / search / startsWith 都是 O(L)，与字典已有词数 n 无关。空间最坏 O(n · L · 26) 指针，实际共享前缀越多越省。
• is_end 不等于"叶子节点"：插入 "app" 与 "apple" 后，"app" 末节点的 is_end = True 但下面还有 l-e 子树；插入 "apple" 末节点也是 is_end = True。判定一个词是否完整存在必须看 is_end，不能用"是否为叶子"代替。
• 字符集变化只改两处：换成 26+10 字母数字 → 数组开 36 槽 + 改 idx 计算；换成稀疏 Unicode → 用 dict 实现 children，其余完全不动。01-Trie 直接把 26 改成 2、按 bit 走即可。

3. 母题精讲

LeetCode 208. 实现 Trie（前缀树）

链接：LeetCode 208

题意：实现一个 Trie 类，支持三个操作：

• insert(word)：把字符串 word 插入字典。
• search(word)：返回 word 是否完整出现在字典里。
• startsWith(prefix)：返回字典里是否存在以 prefix 开头的单词。

数据范围：

• 1 ≤ word.length, prefix.length ≤ 2000
• 每个字符串只包含小写英文字母
• 调用次数最多 3 × 10⁴

示例：

Trie trie = new Trie();
trie.insert("apple");
trie.search("apple");   // 返回 True
trie.search("app");     // 返回 False（"app" 没单独 insert 过）
trie.startsWith("app"); // 返回 True
trie.insert("app");
trie.search("app");     // 返回 True

代码就是 §2 模板的直接套用，不再重复给完整类定义，本节聚焦"插入过程到底发生了什么"。下面把 insert("apple") 一步一步打出来：

node = root
  step 1: c = 'a' → children['a'] 不存在 → 新建; node 下移
  step 2: c = 'p' → children['p'] 不存在 → 新建; node 下移
  step 3: c = 'p' → children['p'] 不存在 → 新建; node 下移
  step 4: c = 'l' → children['l'] 不存在 → 新建; node 下移
  step 5: c = 'e' → children['e'] 不存在 → 新建; node.is_end = True

紧接着 insert("app")：前三步 children['a']、children['p']、children['p'] 都已存在，直接下移、不新建任何节点；最后一步把第二个 p 处的 is_end 标为 True。这就是"前缀共享"的具体体现——只为增量部分付出新节点，重复段白嫖现成路径。

search 和 startsWith 复用同一份 _walk，区别只在末节点要不要校验 is_end。三件套全部 O(L)，与字典已有词数 n 无关。后续 §4 会把这个骨架推广到通配符（LC 211）和最短前缀替换（LC 648）。

4. 例题（三道）

按"基础 → 通配符 → 应用"递进，三段式：先把 LC 208 跑通，再加通配符 DFS（LC 211），最后用 Trie 解一个真实场景题（LC 648）。每道给标准代码 + 关键技巧。

4.1 LC 208 实现 Trie（前缀树）

回到本章开头那道题。代码就是上面模板的直接套用。下面把 insert("apple") 一步一步打出来，看清"沿着字符串走 + 必要时新建节点"是怎么发生的：

node = root
  step 1: c = 'a' → children['a'] 不存在 → 新建; node 下移
  step 2: c = 'p' → children['p'] 不存在 → 新建; node 下移
  step 3: c = 'p' → children['p'] 不存在 → 新建; node 下移
  step 4: c = 'l' → children['l'] 不存在 → 新建; node 下移
  step 5: c = 'e' → children['e'] 不存在 → 新建; node.is_end = True

第二次 insert("app")：前三步 children['a']、children['p']、children['p'] 都已经存在，直接下移，不新建任何节点。最后一步把 pp 处的 is_end 标为 True。这就是"前缀共享"的具体表现——只占用增量节点，重复部分白嫖现成的路径。

search 和 startsWith 用同一个 _walk 帮手——区别只在末节点要不要校验 is_end：

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

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

复杂度速查：

这就是 Trie 相对 HashSet 唯一也是最重要的胜出点：startsWith 和字典里有多少单词无关。下一节看怎么把这个套路推广到通配符。

Follow-up：要是 search 里允许某些位置是通配符 '.'，匹配任意字符呢？

4.2 LC 211 添加与搜索单词

链接：LeetCode 211

题意：实现 WordDictionary 类，支持 addWord(word) 和 search(word)。search 的 word 里可能含字符 '.'，表示通配任意小写字母。

数据范围：

• 1 ≤ word.length ≤ 25
• word 在 addWord 中只含小写字母；在 search 中含小写字母或 '.'
• '.' 在 search 的 word 中至多 3 个
• 调用次数最多 10⁴

示例：

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") → False
search("bad") → True
search(".ad") → True   （'.' 匹配 b 或 d 或 m）
search("b..") → True   （'.' 各匹配一个字母）

通配符让路径不再唯一

LC 208 里 search("app") 沿着 a → p → p 走，路径唯一。LC 211 里 search(".ad")，第一个字符可以是 a/b/c/.../z 中任何一个——路径分叉了。这就是问题的核心。

朴素思路：把所有单词存 set，每次 search 时枚举字典里每个单词、逐位比较是否匹配通配符。时间 O(N · L)，N 是单词数，L 是 word 长度。N = 10⁴ 时勉强能过但不优雅。

在 Trie 上做 DFS 才是这道题的"对路解法"——通配符遇到时把当前节点的所有非空 children 都试一遍，本质就是树上深度优先回溯：

class WordDictionary:
    def __init__(self):
        self.children: list[WordDictionary | None] = [None] * 26
        self.is_end: bool = False

    def addWord(self, word: str) -> None:
        node = self
        for ch in word:
            idx = ord(ch) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = WordDictionary()
            node = node.children[idx]
        node.is_end = True

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

    def _dfs(self, word: str, k: int) -> bool:
        if k == len(word):
            return self.is_end                              # 走完字符串：看末节点是不是单词
        ch = word[k]
        if ch == '.':                                       # 通配符：试每个非空 child
            for child in self.children:
                if child is not None and child._dfs(word, k + 1):
                    return True
            return False
        # 普通字符
        idx = ord(ch) - ord('a')
        child = self.children[idx]
        if child is None:
            return False
        return child._dfs(word, k + 1)

复杂度：

• addWord：O(L)。
• search：最坏 O(26^d × L)，d 是 '.' 的个数。题目限制 d ≤ 3，所以最坏 26³ × 25 ≈ 4 × 10⁵，乘以 10⁴ 次调用约 4 × 10⁹——理论上界看着唬人，但因为字典里只有少数路径真实存在，实际剪枝后远小于这个数。

通配符 DFS 的几个细节

第一，'.' 不要枚举 a-z 所有字符——直接遍历 self.children 数组，跳过 None。如果 children 用 dict 实现就遍历 .values()。这是天然剪枝：一个节点没有的 child 根本不会进入递归。

第二，'.' 也算"消耗一个字符"——递归参数从 k 变 k + 1，跟普通字符一样。容易踩坑的是"通配符跳过当前字符"——不对，'.' 必须匹配恰好一个字符。

第三，为什么不用迭代 + 队列？因为 DFS 写起来比 BFS 短，而且 '.' 个数 ≤ 3 时递归深度顶天 25 层，远低于栈上限。要是 '.' 可以匹配任意长串（变成正则 .*），那就得换 BFS + 状态压缩了——但这道题不是。

Follow-up：上面是给定字符串查询。要是反过来——给一个长字符串和一堆"前缀词典"，要求把这个长字符串里的每个单词替换成它的最短匹配前缀呢？

4.3 LC 648 单词替换

链接：LeetCode 648

题意：给一个"词根字典" dictionary 和一个句子 sentence（空格分词）。对 sentence 里每个单词，如果有词根是它的前缀，就把它替换成最短的那个匹配前缀；否则保留原词。返回处理后的句子。

数据范围：

• 1 ≤ dictionary.length ≤ 1000
• 1 ≤ dictionary[i].length ≤ 100
• 1 ≤ sentence.length ≤ 10⁶
• 都是小写英文字母

示例：

输入：
  dictionary = ["cat","bat","rat"]
  sentence = "the cattle was rattled by the battery"
输出："the cat was rat by the bat"
解释：cattle 被替换成 cat（cat 是它的最短前缀）；rattled → rat；battery → bat。

朴素解：每个单词扫一遍字典

直接对 sentence 每个单词 W 扫整个字典，找出"是 W 前缀"的那些词根、取最短的那个。时间 O(|sentence|/平均词长 × |dictionary| × |W|)，最坏 10⁶ × 10³ × 100 / 5 ≈ 2 × 10¹⁰——TLE 无悬念。

Trie 怎么破？

套路就一句话：把 dictionary 的所有词根 insert 到一棵 Trie 里。然后对 sentence 的每个单词 W，沿着 Trie 走 W 的字符——走到的第一个 is_end = True 节点对应的就是最短匹配前缀：

class TrieNode:
    __slots__ = ("children", "is_end")
    def __init__(self):
        self.children: list[TrieNode | None] = [None] * 26
        self.is_end: bool = False


class Solution:
    def replaceWords(self, dictionary: list[str], sentence: str) -> str:
        root = TrieNode()
        # 建字典
        for root_word in dictionary:
            node = root
            for ch in root_word:
                idx = ord(ch) - ord('a')
                if node.children[idx] is None:
                    node.children[idx] = TrieNode()
                node = node.children[idx]
            node.is_end = True

        def shortest_root(word: str) -> str:
            node = root
            for i, ch in enumerate(word):
                idx = ord(ch) - ord('a')
                if node.children[idx] is None:
                    return word                              # 路径断了，没匹配的前缀
                node = node.children[idx]
                if node.is_end:
                    return word[:i + 1]                      # 命中最短词根
            return word                                      # 整个 word 都走完了还没 is_end

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

复杂度：

• 建 Trie：O(总词根字符数)，最坏 10³ × 100 = 10⁵。
• 处理 sentence：每个单词 O(其长度)，整体 O(|sentence|) = O(10⁶)。

对比朴素 O(2 × 10¹⁰)，Trie 把它降到 O(10⁶)，五个数量级的差距。

为什么"第一个 is_end 就是最短前缀"

按从根出发的路径长度，越浅的 is_end 对应越短的前缀。沿着字符串往下走时，一旦碰到 is_end = True 就立刻返回——返回的就是路径上深度最小的那个标记节点，对应最短匹配。这是 Trie 自然产生的性质，不需要额外维护。换句话说，"最短"这个约束被 Trie 的树形结构白送了。

几个工程细节

__slots__ = ("children", "is_end") 是 Python 的小优化——告诉解释器节点对象不需要 __dict__，每个节点能省 40+ 字节。10⁵ 个节点能省 4MB+ 内存。LC 数据量下不写也能过，但养成习惯。

sentence.split() 默认按空白分词，对题目"空格分词"是正确的。换成真实英文文本，要先处理大小写、标点之类——但这道题不用。

5. 边界、易错与复杂度

is_end 不等于"children 非空"

容易踩坑：很多人把"children 不空"当成"这是个单词"——错了。insert("apple") 后 a → p → p → l → e 五个节点的 children 都至少有一个非 None，但只有 e 这个末节点的 is_end = True。

search("app") 走到 pp 这一层时，is_end = False（因为没单独 insert 过 "app"），所以应该返回 False。这是 search 和 startsWith 行为不同的唯一来源。

字符到下标的转换

数组 children 用 ord(ch) - ord('a') / ch - 'a' 把字符变 0–25 的下标。三个坑：

ord(ch) - ord('a')   # Python：正确
ord(ch - 'a')        # 错！ch - 'a' 在 Python 报 TypeError

ch - 'a'             // Java：正确，char 自动转 int
(int)(ch) - (int)('a')  // 等价但更啰嗦

ch - 'a'             // C++：ch 是 char，自动转 int
                     // 大字符集（含中文等）建议用 unordered_map<char, Trie*>

混入大写 / 数字时立刻越界——题目限定小写字母的话写数组，含大写或符号就用 dict。

共享 root 还是每次 new？

LC 208 的类设计有点特别：每个 Trie 实例本身就是 root，节点和 root 同类型。这是个很巧的写法——children[i] 直接是 Trie | None，递归调用很自然。

工程代码里我更习惯显式 class TrieNode { ... } + class Trie { root: TrieNode; ... }——把"节点"和"持有 root 的类"分开。LC 648 的代码就用了这种写法。两种都能过，看个人偏好。

删除单词

LC 208 不要求 delete，但面试可能问。两种做法：

• 懒删除：把 is_end 改回 False，不动节点结构。简单但内存不释放。
• 真删除：从末节点往回走，递归释放"没有 children 且自己也不是单词末"的节点。代码长，但内存正确回收。

def delete(self, word: str) -> None:
    def rec(node: "Trie", k: int) -> bool:                  # 返回：当前节点是否可被释放
        if k == len(word):
            if not node.is_end:
                return False                                # 单词不在字典
            node.is_end = False
            return all(c is None for c in node.children)
        idx = ord(word[k]) - ord('a')
        child = node.children[idx]
        if child is None:
            return False
        if rec(child, k + 1):
            node.children[idx] = None                       # 释放无用子节点
        return not node.is_end and all(c is None for c in node.children)

    rec(self, 0)

空间复杂度估算

最坏：N 个单词、平均长度 L、字符集大小 σ，且彼此无前缀共享 → O(N × L × σ) 节点指针格。共享后远小于。

LC 208 题目限制：单次操作 L ≤ 2000，最多 3 × 10⁴ 次。最坏 6 × 10⁷ 个字符，每个节点 26 个指针 → 理论上界 1.5 × 10⁹ 指针——Python 撑不住。但实际上字符串"全长 2000 且两两无共享"在 LC 测试里不会出现，过题没问题。

复杂度速查

7. 与相邻数据结构的对比

Trie 不是一个孤岛——下表对比它和几个常被搞混 / 经常一起出现的同族结构：

工程经验：String 字典 + 前缀查询 → Trie；大量重复前缀 → Radix Tree 省内存；多模式串文本搜索 → AC 自动机；只需要 contains 检查 + 内存极紧 → Bloom filter。

8. 小结

Trie 一句话：用一棵树共享前缀——把"一组字符串"压成"一棵树"，每个字符是一条边，每条根到叶的路径是一个单词。它解决的问题 HashSet 解决不了：

• 前缀查询 startsWith 在 O(L) 完成，不依赖字典大小
• 共享前缀的存储节省，N 个长度 L 的单词最坏 O(N × L × σ)，实际共享后远小于
• 沿路径的"末节点"语义灵活——is_end 标记单词、word 字段直接存内容、weight 字段存附加信息（如下标、出现次数）

掌握三件套套路就能套大部分 Trie 题：

• 标准三操作 insert / search / startsWith：模板写到不假思索
• 通配符走 DFS：'.' 类查询枚举所有非空 child，深度有限就不爆
• 01-Trie 处理位运算：整数当 32 位字符串、字符集为 2，所有异或贪心题套这一套

下一节常用数据结构（接下去的章节）会讨论 树状数组与线段树——把"求前缀和 / 区间和"也压到 O(log n)，思路上和 Trie 同源（树形数据结构 + 路径上聚合信息）。

对应灵神题单：常用数据结构 · 字典树（Trie）

进一步阅读：灵茶山艾府《数据结构题单》；LeetCode Trie 标签 高频题；CP-Algorithms《Trie》一节