专题 19Trie 前缀树：把前缀查询做到 O(单词长度)

19.1Trie：把前缀查询做到 O(单词长度)

先用一个场景引出 Trie 的价值。假设词库里有 app、apple、apply 三个词，现在要回答「有没有以 ap 开头的词」。 哈希表得把每个词拿出来看前两个字母，O(词数 × 词长)。Trie 则把它们共享前缀的部分合并成一枝：

Trie 结构（每个节点是一个字符，边是“下一个字符”）：
        (root)
         │ a
         ▼
         a ── p ── p ── l ── e
                          └── y
三个词 app / apple / apply 共享 a→p→p 这一段，后面才分叉。

查「以 ap 开头」：从 root 走 a→p，两步就到，后面有节点 → 存在 ✓
查「是否有 app」：走 a→p→p，且第三个 p 节点标记 isEnd=true → 是完整单词 ✓

Trie 的每个节点代表「走到这里已经拼出的前缀」。节点上通常存两样东西：

• 子节点们：从当前前缀往下还能接哪些字符（常用数组 children[26] 或哈希表）；
• isEnd 标记：当前节点是否代表「某个完整单词的结尾」（区分「前缀存在」和「完整单词存在」）。

Trie 和哈希表，到底差在哪

很多同学会问：「我用一个 HashSet 把所有单词存进去，contains(word) 不也是 O(L) 吗？为什么还要 Trie？」 这个疑问很合理，关键区别在查询的形态：

一句话：HashSet 擅长「精确查一个」，Trie 擅长「前缀相关的批量/模式查询」。前缀补全、拼写检查、路由最长前缀匹配这类活，Trie 是唯一的合理选择。

19.2实现 Trie（前缀树）（中等，力扣 208）

中等 核心：children[26] + isEnd

题意：请你实现一个 Trie，支持三个操作：insert(word) 插入单词、search(word) 查单词是否存在、startsWith(prefix) 查是否有以 prefix 开头的单词。

思路推导：逐字符往下挂

Trie 节点结构：一个长度为 26 的数组 children（假设只含小写字母）和一个布尔 isEnd。

• insert：从根出发，对单词每个字符 c，算出下标 idx = c - 'a'；若 children[idx] 为空就 new 一个节点；然后「走下去」到那个子节点。走完所有字符后，在最后一个节点标 isEnd = true。
• search：同样逐字符往下走，若某步子节点为空说明单词不存在；走完若 isEnd == true 才是「完整单词存在」。
• startsWith：和 search 一样走，但不要求 isEnd——只要能走完 prefix 每个字符（节点都存在）就返回 true。

参考代码

class Trie {
    private Trie[] children;   // 26 个小写字母的子节点
    private boolean isEnd;     // 本节点是否为某个单词结尾

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    // 插入单词：逐字符往下挂，末尾打标记
    public void insert(String word) {
        Trie node = this;                 // 从根（this）出发
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';   // 字符转下标
            if (node.children[idx] == null) {  // 没有这个分支就新建
                node.children[idx] = new Trie();
            }
            node = node.children[idx];         // 往下走一层
        }
        node.isEnd = true;                 // 单词结束，打标记
    }

    // 查找完整单词：必须走到末尾且 isEnd
    public boolean search(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) return false; // 走不下去
            node = node.children[idx];
        }
        return node.isEnd;   // 关键是 isEnd，否则可能只是前缀
    }

    // 查前缀：能走完即可，不要求 isEnd
    public boolean startsWith(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            int idx = prefix.charAt(i) - 'a';
            if (node.children[idx] == null) return false;
            node = node.children[idx];
        }
        return true;   // 走到头说明前缀存在
    }
}

复杂度

每个操作都只走「单词长度 L」步，时间 O(L)；空间是「所有插入单词的字符总数」（每个字符一个节点）。边界：插入空串、重复插入同一单词（isEnd 重设 true 即可，幂等）。

19.3添加与搜索单词（中等，力扣 211）

中等 核心：通配符 '.' 的 DFS 分支

题意：在 19.2 的 Trie 上加一个 search(word) 支持通配符：'.' 可以匹配任意一个小写字母。例如插入 bad、dad、mad 后，search("b..") 应返回 true。

思路推导：遇到 '.' 就分支搜索

insert 和之前完全一样。难点在 search：普通字符就走对应分支；一旦遇到 '.'，它代表「任意一个字母都行」，于是我们要对当前节点的所有 26 个子节点都试一遍——只要有任意一条分支最终能匹配完剩余字符，就返回 true。这正是DFS（深度优先搜索）的用武之地。

插入 bad / dad / mad 后，搜 "b.."：
  b → 确定走 b 分支
  . → 枚举 b 节点的所有子节点（这里只有 a）
  . → 枚举 a 节点的所有子节点（d）→ 走完且 isEnd → true
如果有多个子节点（比如 b 下有 a 和 o），两条都要试，任一成功即成功。

参考代码

class WordDictionary {
    private WordDictionary[] children;
    private boolean isEnd;

    public WordDictionary() {
        children = new WordDictionary[26];
        isEnd = false;
    }

    public void addWord(String word) {
        WordDictionary node = this;
        for (int i = 0; i < word.length(); i++) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new WordDictionary();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        return dfs(this, word, 0);
    }

    // 从 node 开始，匹配 word 的第 i 个字符起
    private boolean dfs(WordDictionary node, String word, int i) {
        if (i == word.length()) return node.isEnd; // 走完，看是否完整单词
        char c = word.charAt(i);
        if (c != '.') {
            // 普通字符：只走对应分支
            int idx = c - 'a';
            return node.children[idx] != null
                && dfs(node.children[idx], word, i + 1);
        } else {
            // 通配符 '.'：枚举所有非空子节点，任一成功即可
            for (int j = 0; j < 26; j++) {
                if (node.children[j] != null
                    && dfs(node.children[j], word, i + 1)) {
                    return true;   // 剪枝：找到一条就够
                }
            }
            return false;  // 所有分支都失败
        }
    }
}

复杂度

最坏情况下（全是 '.'），每个 '.' 展开 26 个分支，复杂度约 O(26^L)——但 L 通常很小，实际可接受。insert O(L)。边界：空串、全是 '.' 的搜索都按逻辑正常处理。

19.4单词搜索 II（困难，力扣 212，选学）

困难 核心：网格 DFS + Trie 同时走（选学）

题意：在一个 m×n 字母网格里，找出所有能被拼出的词典单词。每个格子只能上下左右走、不能重复使用同一格。例如网格里有 o,a,n 等组成，词典 ["oath","pea","rain"]，返回能拼出的那些。

思路推导：把「每个单词都搜一遍」优化成「Trie 一起走」

暴力思路：对词典里每个单词，从网格每个格子开始 DFS 尝试拼。复杂度约 O(w·m·n·4^L)，w 是词数、L 是词长，显然太慢——同一个前缀 oa 被不同单词反复从网格重搜。

优化思路：把所有词典单词建一棵 Trie，然后让网格 DFS 和 Trie 同时走。从网格某格出发，每走到一个字母，就沿 Trie 往对应子节点走一步；当 Trie 走到某个 isEnd 节点，说明当前拼出的路径正好是词典里一个单词，收入答案。这样共享前缀的单词只搜一次，复杂度降到 O(m·n·4^L)（与词数 w 无关！）。

为什么非得 Trie？一个具体数字

假设词典有 w=10 万个单词，平均长度 L=8，网格 10×10。暴力做法要对每个单词从 100 个格子起手 DFS，约 10^5 × 100 × 4^8 ≈ 6.5×10^12 次操作，根本跑不完。 而 Trie 方案：无论词典多大，网格 DFS 总次数只和「网格大小 × 每步分支」有关，约 100 × 4^8 ≈ 6.5×10^5——差了上百万倍。差距来源就是「共享前缀只搜一次」。

参考代码（核心框架）

// 思路骨架（省略 Trie 定义，复用 19.2 的结构）：
// 1. 把所有单词 insert 进 Trie
// 2. 对网格每个格子 (i,j) 起手 DFS，同时带着当前 Trie 节点走
// 3. 走到 Trie 的 isEnd 节点 → 收集该单词；走过格子标记为已访问避免回头
// 4. 上下左右四方向继续，回溯时恢复访问标记

// 关键片段（在 DFS 中）：
//   char c = board[i][j];
//   int idx = c - 'a';
//   Trie next = cur.children[idx];
//   if (next == null) return;        // 这条拼法词典里没有，剪枝
//   if (next.isEnd) ans.add(next.word);  // 拼出一个完整单词
//   board[i][j] = '#';               // 标记已用
//   dfs(board, i+1,j, next); ... 四方向
//   board[i][j] = c;                 // 回溯

复杂度

网格每个起点一次 DFS，每步 4 方向，深度 ≤ 最长词 L，约 O(m·n·4^L)；建 Trie O(总字符数)。相比暴力 O(w·m·n·4^L)，当 w 大时优势巨大。

19.5Trie 的应用场景总结

Trie 不是银弹，它专门吃「前缀相关」的活儿。一张表看清什么时候该上 Trie：

什么时候【不用】Trie，改用 HashMap：
  · 字符集很大（中文/任意 Unicode）→ 节点数组爆内存，HashMap 更省
  · 单词数量很少、且只查「完整单词」→ 直接 HashSet 即可，O(1)
  · 不需要前缀能力 → Trie 的空间浪费不划算

一个直觉类比：电话簿 vs 通讯录搜索框

把 Trie 想象成老式电话簿：按首字母分 section，A 开头的全堆在 A 区，再按第二个字母细分。你要找「以 Li 开头的所有人」，直接翻到 L→i 那一块，整块都是，不用扫全书。 HashSet 则像一张没有排序的名片盒，查「名片上有没有叫张三的」很快，但要「所有姓 Li 的」就得一张张翻——这就是前缀能力的差距。

19.6本专题常见坑

19.7自测题