LeetCode 212. 单词搜索 II
目录
题目描述
题意分析
给一个由小写字母组成的二维网格和一份单词表，要求返回单词表中所有能在网格里「走出来」的单词。走的规则是从任意格子出发，每步只能移动到上下左右相邻的格子，并且同一条路径上每个格子最多用一次。
输出的是单词列表而不是路径，所以同一个单词无论有多少种走法，都只算一次；不同单词之间没有互相影响。
约束信号很关键：网格最大 $12 \times 12$，但单词数量最多 $3 \times 10^4$，每个单词最长 10 个字符，且全部由小写字母构成。单词数远大于格子数，说明「对每个单词跑一次网格搜索」的代价主要压在单词数量上，需要把大量单词共享的公共前缀合并起来。
边界情况：单词表里可能有重复单词，答案不能重复输出；单词长度可能超过网格总格子数，此时必然搜不到；单个字符的单词只要网格里存在该字符即成立。
解法：Trie 前缀树 + 回溯搜索
核心思路
如果对每个单词单独做一次网格回溯，像
oath、oatx、oaty这样共享oat前缀的单词，会把同一段网格路径重复搜索多次。单词数最多为 $3 \times 10^4$，这个重复因子才是瓶颈。将所有单词放入 Trie，然后反过来从网格的每个格子出发。搜索每向前走一格，就沿 Trie 向下走一层：若对应孩子不存在，当前网格路径不是任何候选单词的前缀，立即停止。这样一条网格路径能同时服务所有共享该前缀的单词。
Trie 终止节点直接保存完整单词，而不是只存布尔标记。搜索命中时可直接加入答案，不需要另外拼接路径字符。加入后把
word置空，使同一个单词即使在网格中有多条路径，也只输出一次。还可以做一层不增加算法难度的动态剪枝：每个 Trie 节点记录非空孩子数
childCount。回溯返回时，如果当前节点已没有未报告的单词，也没有孩子，就从父节点删掉这条边。一条 Trie 分支被删除，意味着这个前缀下的所有单词都已找到；后续起点再遇到同样前缀时，可在更浅的层数直接返回。剪掉的不是「这条网格路径当前走不通」的分支，而是「候选单词已全部消耗」的分支，所以不会漏解。回溯不变量：进入
dfs(row, col, parent)时，已被改成#的格子恰好是当前路径中、但不包含(row, col)的格子；parent恰好对应已走过字符构成的 Trie 前缀。若parent.children[board[row][col]]存在，进入孩子后两者同步向前一步；递归前标记、返回后恢复，保证同一格子在一条路径内最多使用一次，但不影响其他路径。正确性：搜索只在 Trie 存在对应边时前进，因此每个被加入的字符串都来自一条合法网格路径，且是单词表中的终止节点，不会多报。反之，任意可在网格中走出的候选单词，从它的起点出发时，DFS 会沿其合法路径和 Trie 边逐字符前进，直到终止节点；未找到的单词节点不会被动态删除，因此不会漏报。
word命中后置空，保证每个答案只报告一次。
解题步骤
- 建 Trie：逐字符插入每个单词。只有创建新孩子时才增加
childCount，并在终止节点保存完整单词。- 枚举起点：网格中的每个格子都可能是单词首字母，所以从每个位置调用
dfs，传入 Trie 根节点作为父节点。- 过滤无效状态：DFS 先判断越界和
#，再查找当前字符对应的 Trie 孩子。孩子不存在就返回，这是基于「不是任何单词前缀」的核心剪枝。- 收集单词：若孩子节点的
word非空，将其加入答案后立即置空。这只是消耗当前完整单词，不能立即返回：例如找到"oat"后仍要继续搜索"oath"。- 回溯四个方向：把当前格子改成
#，向上下左右递归，再恢复原字符。原地标记避免额外的visited数组，恢复则确保其他起点和分支仍能使用该格子。- 删除耗尽分支：四个方向都搜完后，若
node.word为空且node.childCount == 0，说明该前缀下所有候选都已找到。将parent.children[index]置空，并减少父节点的孩子数。用经典样例走查剪枝：
board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]，words = ["oath","pea","eat","rain"]。从 $(0,0)$ 的o出发，向下遇到e时，Trie 的o节点下没有e，立刻剪枝；向右按o-a-t-h走到 $(2,1)$ 则命中"oath"。将终止节点的word置空后，h节点已无单词且无孩子，回溯时依次删掉h、t、a、o边。之后任意起点遇到o，在根节点就能返回，不会重复搜索已经耗尽的oath分支。继续从 $(1,3)$ 的
e经 $(1,2)$ 的a走到 $(1,1)$ 的t，找到"eat"。"pea"和"rain"没有合法路径，它们的 Trie 终止标记一直保留，不会因为某次路径失败就被错误删除。最终答案为["oath", "eat"]。
代码实现
import java.util.ArrayList;
import java.util.List;
class Solution {
private static final int[][] DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public List<String> findWords(char[][] board, String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
insert(root, word);
}
List<String> res = new ArrayList<>();
for (int row = 0; row < board.length; row++) {
for (int col = 0; col < board[0].length; col++) {
dfs(board, row, col, root, res);
}
}
return res;
}
private void dfs(char[][] board, int row, int col, TrieNode parent, List<String> res) {
if (row < 0 || row >= board.length || col < 0 || col >= board[0].length || board[row][col] == '#') {
return;
}
char ch = board[row][col];
TrieNode node = parent.children[ch - 'a'];
if (node == null) {
return;
}
if (node.word != null) {
res.add(node.word);
node.word = null;
}
board[row][col] = '#';
for (int[] direction : DIRECTIONS) {
dfs(board, row + direction[0], col + direction[1], node, res);
}
board[row][col] = ch;
// 该前缀下的单词已全部找到，后续不再搜索这条分支。
if (node.word == null && node.childCount == 0) {
parent.children[ch - 'a'] = null;
parent.childCount--;
}
}
private void insert(TrieNode root, String word) {
TrieNode node = root;
for (int i = 0; i < word.length(); i++) {
int idx = word.charAt(i) - 'a';
if (node.children[idx] == null) {
node.children[idx] = new TrieNode();
node.childCount++;
}
node = node.children[idx];
}
node.word = word;
}
private static class TrieNode {
private final TrieNode[] children = new TrieNode[26];
private int childCount;
private String word;
}
}
type TrieNode struct {
children [26]*TrieNode
childCount int
word string
}
func findWords(board [][]byte, words []string) []string {
root := &TrieNode{}
for _, word := range words {
insertWord(root, word)
}
res := make([]string, 0)
directions := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
var dfs func(row int, col int, parent *TrieNode)
dfs = func(row int, col int, parent *TrieNode) {
if row < 0 || row >= len(board) || col < 0 || col >= len(board[0]) || board[row][col] == '#' {
return
}
ch := board[row][col]
node := parent.children[ch-'a']
if node == nil {
return
}
if node.word != "" {
res = append(res, node.word)
node.word = ""
}
board[row][col] = '#'
for _, direction := range directions {
dfs(row+direction[0], col+direction[1], node)
}
board[row][col] = ch
// 该前缀下的单词已全部找到，后续不再搜索这条分支。
if node.word == "" && node.childCount == 0 {
parent.children[ch-'a'] = nil
parent.childCount--
}
}
for row := 0; row < len(board); row++ {
for col := 0; col < len(board[0]); col++ {
dfs(row, col, root)
}
}
return res
}
func insertWord(root *TrieNode, word string) {
node := root
for i := 0; i < len(word); i++ {
idx := word[i] - 'a'
if node.children[idx] == nil {
node.children[idx] = &TrieNode{}
node.childCount++
}
node = node.children[idx]
}
node.word = word
}
复杂度分析
设 $m$ 和 $n$ 为网格行列数，$S = \sum \lvert word_i\rvert$ 为单词总字符数，$L$ 为最长单词长度。
- 时间复杂度：建 Trie 需要 $O(S)$。网格搜索的最坏上界是 $O(mn \cdot 4 \cdot 3^{L-1})$：每个格子都可作起点，起点后首步最多向 4 个方向扩展，之后由于不能走回来路，每层最多剩 3 个方向，深度不超过 $L$。因此总上界为 $O(S + mn \cdot 4 \cdot 3^{L-1})$。这是忽略 Trie 剪枝的极端上界；实际中「不是候选前缀」与「已找完分支删除」会大幅缩小搜索树，但不改变最坏上界。
- 空间复杂度：$O(S + L)$。Trie 最多为每个单词字符创建一个节点，占 $O(S)$；回溯栈深度最多是 $L$。网格被原地标记后恢复，不需要 $O(mn)$ 的访问数组。返回结果空间不计入辅助空间。
关键点总结
- 单词数远大于网格规模时，关键是合并重复的前缀搜索。Trie 把「当前路径还是否可能成词」变成 $O(1)$ 的孩子查找。
- 回溯状态有两个同步部分：网格路径用
#标记已用格子，Trie 节点表示当前字符前缀。每走一格，两个状态必须同时前进。- 终止节点保存完整单词，命中时既无需拼接路径，又能通过置空在源头去重。但命中一个单词不代表该前缀已结束，还要继续寻找更长单词。
- 动态剪枝只能删除「
word为空且没有孩子」的节点。这个条件表示整个前缀分支已经耗尽，而不是某条网格路径暂时失败。childCount把「是否仍有孩子」从每次扫描 26 个指针变成 $O(1)$ 判断；只在新建或真正删除一条 Trie 边时更新，才能保持准确。- 面试表达顺序可以是：先指出「逐单词回溯重复搜公共前缀」，再用 Trie 合并前缀，最后说明命中去重和耗尽分支删除，层次比直接背代码更清楚。
易错点总结
- 命中单词就直接返回：
words = ["oat", "oath"]时，走到oat只是命中了较短单词，还必须继续向孩子搜索oath。只有当节点没有孩子时，才能确定该前缀无更长候选。- 找到单词后不清空
word：board = [["a","a"]], words = ["a"]会从两个起点各命中一次，输出重复的"a"。终止标记必须在首次命中时消耗。- 进入标记后忘记恢复网格：
board = [["a","b"]], words = ["ab","ba"]中，搜完"ab"后若a仍为#，后续从b出发就无法找到"ba"。标记与恢复必须成对。- 在越界检查前读取网格：四方向递归天然会生成越界坐标；先取
board[row][col]会直接越界。检查顺序必须是坐标、访问标记、Trie 孩子。- 递归时仍传
parent：words = ["ab"]且网格中a、b相邻时，走到b应在 Trie 的a节点下查找；若仍传父节点，网格路径与 Trie 前缀就会错位。- 只因某条网格路径失败就删 Trie 分支：当前起点走不通，不代表其他起点也走不通。只能在
word已空且childCount == 0时删除，因为这个状态才证明该分支下已无未找到单词。childCount更新不对称：插入重合前缀时对旧孩子重复加一，或剪枝时没有减一，都会让叶子判断失真。只有指针从null变为节点时加一，从节点变为null时减一。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 79. 单词搜索 | 中等 | 单个模式串的网格回溯，不需要前缀树 |
| 208. 实现 Trie (前缀树) | 中等 | 前缀树本身的插入、查找与前缀判定 |
| 211. 添加与搜索单词 - 数据结构设计 | 中等 | 前缀树上带通配符的搜索，需在节点处分叉 |
| 1219. 黄金矿工 | 中等 | 网格回溯求路径权值最大值，剪枝依据是数值 |
| 980. 不同路径 III | 困难 | 要求恰好覆盖全部可走格子，靠剩余格数剪枝 |