LeetCode 212. 单词搜索II——Trie+DFS回溯的剪枝与内存优化

适读人群：Java中高级工程师、算法竞赛选手、系列终结篇 | 阅读时长：约28分钟 | 难度：困难

---

开篇故事

终于到了第600篇。这道"单词搜索 II"是整个贪心、回溯与排列组合系列的收官之作，也是这20篇文章中最复杂的一道。

它是单词搜索 I（LeetCode 79）的升级版：从搜索一个单词变成搜索一组单词。暴力方法是对每个单词分别调用 LeetCode 79 的解法，但 words 最多有 30000 个单词，这样做会超时。

优化的关键是 Trie（前缀树）：把所有单词构建成一棵 Trie，然后只做一次 DFS 遍历整个网格，每到一个格子就在 Trie 上前进一步。如果当前路径对应的前缀在 Trie 中存在，继续向下搜索；如果不存在，立刻剪枝。这样，所有单词的搜索被合并成了一次遍历，而 Trie 的前缀剪枝确保了效率。

更精妙的是内存优化：当 Trie 中某个单词的所有节点都已经被找到并输出后，可以从 Trie 中删除该单词节点（"剪叶子"），避免重复搜索。这个细节在 words 有大量重复前缀时能显著减少搜索开销。

今天把这道题讲透，也是对这一系列 20 篇文章的一个完美收尾。

---

一、题目解析

题目： 给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，返回所有二维网格上的单词。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中相邻单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。

示例：

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

关键数字（约束）：

• m, n <= 12（网格规模中等）
• words.length <= 3 * 10^4（单词数量大）
• 每个单词长度 <= 10

暴力方法的问题：

对每个单词调用一次 79 题的解法，时间复杂度：O(|words| × m × n × 4^L)，其中 L 是最长单词长度。|words|=30000，m=n=12，L=10 → 约 30000 × 144 × 4^10 = 天文数字，完全不可行。

Trie 优化的本质：

将所有单词的前缀共享。如果某个路径的前缀在所有单词中都不存在，立刻剪枝，不需要继续往下走。等于把"30000次独立搜索"合并成了"1次共享前缀的搜索"。

---

二、解法一：暴力（对每个单词调用LeetCode 79）

代码（超时参考）

import java.util.*;

public class Solution_Brute {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<>();
        for (String word : words) {
            if (exist(board, word)) result.add(word);
        }
        return result;
    }
    
    private boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (dfs(board, word, r, c, 0, m, n)) return true;
            }
        }
        return false;
    }
    
    private boolean dfs(char[][] board, String word, int r, int c, int idx, int m, int n) {
        if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(idx)) return false;
        if (idx == word.length() - 1) return true;
        char orig = board[r][c]; board[r][c] = '#';
        boolean found = dfs(board,word,r+1,c,idx+1,m,n) || dfs(board,word,r-1,c,idx+1,m,n)
                     || dfs(board,word,r,c+1,idx+1,m,n) || dfs(board,word,r,c-1,idx+1,m,n);
        board[r][c] = orig;
        return found;
    }
}

时间复杂度： O(|words| × m × n × 4^L)，超时。

---

三、解法二：Trie + DFS（标准最优解）

Trie 节点设计

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word = null; // 非null时表示这里是某个单词的结尾
}

注意：直接在叶子节点存储单词字符串（而不是布尔标记），这样找到单词后可以直接添加到结果，不需要额外传递当前路径。

DFS + Trie 剪枝

DFS 时，当前节点对应 Trie 中的某个节点，每次沿 board 移动时，同时在 Trie 中向下走一步。如果 Trie 中没有对应字符的子节点，该方向剪枝。

代码

import java.util.*;

public class Solution {
    private int m, n;
    private int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    
    public List<String> findWords(char[][] board, String[] words) {
        m = board.length;
        n = board[0].length;
        
        // 构建 Trie
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode node = root;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                if (node.children[idx] == null) {
                    node.children[idx] = new TrieNode();
                }
                node = node.children[idx];
            }
            node.word = word; // 在单词末尾节点存储单词
        }
        
        List<String> result = new ArrayList<>();
        
        // 遍历每个格子作为起点
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                dfs(board, r, c, root, result);
            }
        }
        
        return result;
    }
    
    private void dfs(char[][] board, int r, int c, TrieNode node, List<String> result) {
        // 边界检查
        if (r < 0 || r >= m || c < 0 || c >= n) return;
        
        char ch = board[r][c];
        if (ch == '#') return; // 已访问
        
        TrieNode nextNode = node.children[ch - 'a'];
        if (nextNode == null) return; // Trie 中无此前缀，剪枝
        
        // 找到一个单词
        if (nextNode.word != null) {
            result.add(nextNode.word);
            nextNode.word = null; // 置null，防止重复添加同一单词
        }
        
        // 原地标记当前格子
        board[r][c] = '#';
        
        // 向四方向搜索
        for (int[] d : dirs) {
            dfs(board, r + d[0], c + d[1], nextNode, result);
        }
        
        // 回溯：恢复格子
        board[r][c] = ch;
        
        // 内存优化：若 nextNode 已无子节点且不是单词结尾，从 Trie 中删除（"剪叶子"）
        // 可选优化，见解法三
    }
    
    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null;
    }
}

Mermaid 图：Trie + DFS 的工作原理

复杂度分析

• 时间复杂度： O(m × n × 4^L × |Σ|)，其中 |Σ|=26（Trie 子节点数），L 是最长单词长度。实际远小于此，因为 Trie 的前缀剪枝大幅减少了搜索树。
• Trie 构建： O(Σ|words| × 每词长度) = O(|words| × L)。
• 空间复杂度： O(|words| × L)（Trie 空间）+ O(L) 递归栈。

---

四、解法三：Trie + DFS + 剪叶子优化

剪叶子思路

当一个 Trie 节点的所有子节点都为 null，且 word = null（不是任何单词的结尾），这个节点就是"无用叶子"，可以从父节点删除。

删除时机：在 DFS 回溯时，检查 nextNode 是否还有子节点（hasChildren 方法），如果没有，将父节点对应的 children[idx] 置为 null。

代码（完整优化版）

import java.util.*;

public class Solution_Optimized {
    private int m, n;
    private int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    
    public List<String> findWords(char[][] board, String[] words) {
        m = board.length;
        n = board[0].length;
        
        TrieNode root = buildTrie(words);
        List<String> result = new ArrayList<>();
        
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                dfs(board, r, c, root, result);
            }
        }
        
        return result;
    }
    
    private void dfs(char[][] board, int r, int c, TrieNode parent, List<String> result) {
        if (r < 0 || r >= m || c < 0 || c >= n) return;
        char ch = board[r][c];
        if (ch == '#') return;
        
        int idx = ch - 'a';
        TrieNode node = parent.children[idx];
        if (node == null) return;
        
        if (node.word != null) {
            result.add(node.word);
            node.word = null; // 找到后清除，防重复
        }
        
        board[r][c] = '#'; // 标记访问
        
        for (int[] d : dirs) {
            dfs(board, r + d[0], c + d[1], node, result);
        }
        
        board[r][c] = ch; // 回溯
        
        // 剪叶子优化：若 node 已无子节点且不是单词结尾，从 parent 中删除
        if (node.word == null && !node.hasChildren()) {
            parent.children[idx] = null;
        }
    }
    
    private TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String word : words) {
            TrieNode cur = root;
            for (char c : word.toCharArray()) {
                int idx = c - 'a';
                if (cur.children[idx] == null) cur.children[idx] = new TrieNode();
                cur = cur.children[idx];
            }
            cur.word = word;
        }
        return root;
    }
    
    static class TrieNode {
        TrieNode[] children = new TrieNode[26];
        String word = null;
        
        boolean hasChildren() {
            for (TrieNode child : children) {
                if (child != null) return true;
            }
            return false;
        }
    }
}

剪叶子的效果

假设 words 中有大量短单词，如 ["a","b","c","ab","ac"...]。在找到这些单词后，对应的 Trie 节点变成了"无效叶子"，"剪叶子"后这些节点不再参与后续的 DFS 判断，减少了 Trie 的规模，提升后续搜索效率。

在最坏情况（所有单词都很长且不共享前缀），剪叶子没有帮助，但实际中大多数单词集都有共享前缀，效果显著。

复杂度分析

• 时间复杂度： 理论上界不变，但实际运行时间因剪叶子显著减少（特别是 words 较多时）。
• 空间复杂度： O(|words| × L)，Trie 会随着搜索进行而动态缩减。

---

五、举一反三

Trie 的适用场景

Trie（前缀树）在以下场景中特别有优势：

1. 前缀查询：判断一个字符串是否是某些字符串的前缀，O(L) 时间。
2. 多模式匹配：同时在文本中搜索多个模式字符串（本题、Aho-Corasick 算法）。
3. 字符串排序：Trie 的 DFS 遍历自动按字典序输出。
4. 自动补全/搜索建议：从 Trie 找以给定前缀开头的所有字符串。

本题与 LeetCode 79 的代码对比

特性	LeetCode 79	LeetCode 212
搜索目标	单个字符串	多个字符串
匹配方式	逐字符比较	Trie 节点跳转
剪枝方式	字符不匹配时停止	Trie 子节点为null时停止
找到结果	返回true	加入结果集，继续搜索
回溯后处理	无	可选"剪叶子"

---

六、踩坑实录

坑一：找到单词后不置null导致重复添加

网格中可能有多条路径都能拼出同一个单词（例如 board 中有两个 'a'，单词是 "a"）。找到单词后立刻将 node.word = null 是防止重复添加的关键。

坑二：剪叶子时机错误

剪叶子必须在 DFS 回溯之后（board[r][c] = ch 之后），而不是在 DFS 过程中。如果在递归进行中就删除节点，会导致同一路径上的其他格子（它们也会进入这个节点的子树）找不到节点。

坑三：Trie 节点用数组还是 HashMap

用 TrieNode[26] 数组的优点：O(1) 的子节点访问，内存预分配整齐；缺点：每个节点固定分配 26 个指针，当字符集大时浪费内存。

如果字符集很大（如 Unicode），用 HashMap<Character, TrieNode> 更省内存，但访问速度略慢。对于本题（只有小写字母），数组更优。

坑四：board 的修改是否影响后续 for 循环

主函数中的双重 for 循环枚举起点，每次 DFS 结束后 board 已完全恢复（通过回溯），所以每个起点都在一个干净的 board 上开始搜索，不会相互干扰。

坑五：hasChildren() 方法的复杂度

hasChildren() 遍历 26 个子节点，是 O(26) = O(1) 的操作。但如果每次 DFS 回溯都调用，且调用次数很多，累计开销不可忽视。一个优化是给 TrieNode 加一个 childCount 计数器，O(1) 检查是否有子节点。

---

七、总结与系列收尾

单词搜索 II 是回溯+数据结构（Trie）结合的经典范例，也完美诠释了"用合适的数据结构加速搜索"的设计思路。

核心优化点：

1. Trie 替代逐字比较：O(1) 的前缀查询，多单词共享搜索路径。
2. 原地标记替代 visited 数组：节省 O(m×n) 空间。
3. found 后清空 node.word：防止重复添加。
4. 剪叶子：已找到的单词节点从 Trie 中删除，动态缩减搜索空间。

---

至此，贪心、回溯与排列组合精讲系列（第 581-600 期）圆满完成。回顾这20篇的路径：

贪心篇（581-587）：

• 从最简单的分发饼干讲起，核心是"交换论证法"证明贪心正确性。
• 区间类贪心：无重叠区间、合并区间、引爆气球，掌握"按结束时间排序"的核心策略。
• 特殊贪心：加油站的总量判断、身高重建的多维排序、划分字母区间的动态右边界。

回溯篇（588-600）：

• 全排列、子集、组合：回溯的三大基础场景，掌握 visited 数组和 start 参数的用法。
• 去重系列：全排列II、子集II、组合总和II，深入理解 i > start && nums[i]==nums[i-1] 的含义。
• 进阶回溯：分割回文串（DP预处理）、解数独和N皇后（位运算优化）、单词搜索系列（DFS+Trie）。

章节	代表题	核心技巧
贪心	455/435/134	交换论证、最优子结构证明
基础回溯	46/78/77	模板建立、剪枝策略
去重回溯	47/90/40	i>start、visited区分层
高级回溯	37/51/212	位运算、Trie加速

---

补充深入讲解：字典树与DFS的协同设计

为什么单词搜索 II 不能简单重复单词搜索 I

LeetCode 79（单词搜索 I）对单个单词做 DFS，时间复杂度是 O(m×n×3^L)，L 是单词长度。如果有 K 个单词，朴素做法是对每个单词独立调用 LeetCode 79 的算法，总时间复杂度是 O(K×m×n×3^L)。

当 K 较大时（题目中最多 10000 个单词），这个复杂度是不可接受的。Trie 的价值在于：将 K 个单词共享的前缀合并，一次 DFS 同时搜索所有单词，而不是每个单词独立搜索。

具体地说，当 DFS 到达棋盘上的某个位置时，我们在 Trie 中也到达了对应的节点。如果这个 Trie 节点不存在（即当前路径不是任何单词的前缀），直接剪枝，不需要继续搜索。这一个剪枝就覆盖了所有以当前路径为前缀的单词，比逐个单词独立搜索高效得多。

Trie 的构建与搜索过程详解

构建 Trie：遍历所有单词，每个字符为一个节点。TrieNode 有 26 个子节点（对应 26 个字母）和一个标记（当该节点是某个单词末尾时，存储该单词或设置 isEnd 标志）。

DFS 与 Trie 的协同：DFS 从棋盘的某个起点出发，同时在 Trie 中从根节点出发，每走一步棋盘格子，就在 Trie 中沿着对应字母的边走一步。如果 Trie 中没有对应的边，说明当前路径不是任何单词的前缀，立即剪枝（不需要继续探索这个方向）。如果到达某个 Trie 节点，它标记了一个单词的结尾，则记录这个单词为找到的结果。

这个过程的优势：多个单词的共同前缀只被搜索一次。例如 words=["apple","apply","application"]，前缀 "appl" 只被探索一次，而不是三次。

内存优化：搜到后从 Trie 中删除

一旦找到某个单词，如果不对 Trie 做处理，后续 DFS 中遇到同一个单词的另一个路径时，还会重复添加到结果集（需要手动去重）。更优雅的做法是：找到单词后，将 Trie 中该单词末尾节点的标记清除（node.word = null），这样同一个单词不会被重复找到，无需额外去重。

进一步的优化是"删除叶节点"：如果一个 Trie 节点既没有子节点，又没有标记单词（已经被清除），那么这个节点是"无用的死节点"，可以从 Trie 中删除（将其父节点的对应子节点设为 null）。这样在 DFS 过程中，Trie 的大小会随着单词被找到而逐渐缩小，减少无效的 Trie 节点遍历，提高后续搜索速度。这是很多高分提交使用的优化技巧。

Trie 的替代数据结构：哈希表前缀树

在 Java 实现中，TrieNode 用数组 children[26] 比用 HashMap<Character, TrieNode> 更快，因为数组访问是 O(1) 的简单偏移，而 HashMap 需要哈希计算和潜在的冲突处理。

但数组方式的空间是固定的 26 个引用，即使大多数子节点为 null，也占用空间（26个引用 × 8字节 = 208字节/节点）。对于字符集较大的情况（如 Unicode），HashMap 方式更节省空间。对于只含 26 个小写字母的题目，数组方式是标准选择。

从单词搜索到 AC 自动机

Trie + DFS 是处理"在文本中搜索多个模式串"问题的基础技术。这道题的棋盘搜索是其中一种场景，另一种更常见的场景是在普通文本（线性字符串）中搜索多个关键词。

对于线性文本的多模式搜索，有一个比 Trie + DFS 更高效的算法：AC 自动机（Aho-Corasick Automaton），由 Alfred Aho 和 Margaret Corasick 在1975年提出。AC 自动机在 Trie 的基础上增加了"失败链接"（failure links），使得在文本中遇到不匹配时，能快速跳转到下一个可能的匹配起点，而不需要重新从头开始。AC 自动机的时间复杂度是 O(n + m + z)，n 是文本长度，m 是所有模式串总长度，z 是匹配结果数量——这是多模式搜索的理论最优。

在实际工程中，AC 自动机被广泛用于敏感词过滤（在大量用户内容中检测违禁词汇）、日志分析（在海量日志中搜索多个异常模式）、生物信息学（在基因序列中搜索多个特征序列）。

理解了单词搜索 II 中 Trie 的作用，再学习 AC 自动机就有了很好的基础。两者都是"把多个模式串组织成树状结构，同时搜索文本"的思想，区别在于搜索文本的方式（DFS 网格 vs 线性扫描）和处理不匹配的方式（回溯 vs 失败链接跳转）。

---

单词搜索 II 的学习价值与总结

单词搜索 II（LeetCode 212）是回溯专题中难度最高的题目之一，它综合考察了 Trie 数据结构、DFS 回溯、原地标记、边界处理等多个知识点。这道题是面试中的高频"压轴题"，通常出现在高级工程师面试或技术难度较高的公司面试中。

解决这道题的过程，其实是把多个算法知识点融合应用的过程。Trie 负责高效的前缀匹配和多模式管理，DFS 回溯负责在棋盘上探索所有可能的路径，原地标记避免了额外的 visited 数组，找到后删除 Trie 节点避免了结果重复。每一个优化都有其存在的理由，缺少任何一个都会导致超时或错误。

在准备面试时，如果时间有限，可以先掌握 LeetCode 79（单词搜索 I），再学 LeetCode 212。212 的核心是"用 Trie 把多个单词的查找合并"，在理解了 79 的 DFS 框架之后，只需理解 Trie 的作用和 DFS 与 Trie 的协同方式，就能写出 212 的代码。

最终，212 题考查的不只是会写 Trie 和 DFS，更考查能否在面试的压力下理清多个数据结构的协作关系，设计出正确且高效的算法。这需要大量的练习和对算法本质的深刻理解。