单词搜索 II 为什么要用 Trie + DFS 回溯？

简化版

把单词表建成 Trie，再从棋盘每个格子出发做 DFS。DFS 过程中按当前路径在 Trie 中向下走，一旦 Trie 没有对应孩子就立刻剪枝；走到 isEnd 节点就找到一个单词。

详细版

单词搜索 II 的暴力做法是对每个单词单独在棋盘上 DFS，复杂度会非常高。Trie 的作用是把所有单词共享前缀，DFS 棋盘时同时匹配整个词典。

核心步骤：

把 words 全部插入 Trie，终止节点保存完整单词或单词编号。
从棋盘每个格子 (r,c) 开始 DFS。
当前字符 board[r][c] 必须能走到 Trie 的某个孩子，否则剪枝。
若走到的 Trie 节点是某个单词结尾，把单词加入答案。
继续向上下左右扩展，访问过的格子要临时标记，回溯时恢复。

void dfs(char[][] board, int r, int c, Trie node, Set<String> ans) {
    if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) return;
    char ch = board[r][c];
    if (ch == '#' || node.children[ch - 'a'] == null) return;

    Trie next = node.children[ch - 'a'];
    if (next.word != null) {
        ans.add(next.word);
    }

    board[r][c] = '#';
    dfs(board, r + 1, c, next, ans);
    dfs(board, r - 1, c, next, ans);
    dfs(board, r, c + 1, next, ans);
    dfs(board, r, c - 1, next, ans);
    board[r][c] = ch;
}

如果棋盘大小为 R*C，单词最大长度为 L，Trie 剪枝后实际复杂度取决于可走路径数量，通常远小于“每个单词单独 DFS”。

完整版教学

一、暴力为什么会爆炸

假设棋盘是 12 x 12，单词表有 3000 个词，每个词最长 10。如果对每个单词都单独从每个格子出发 DFS，就会重复探索大量相同前缀路径。例如 oath、oat、oar 都以 oa 开头，暴力会为每个词反复走棋盘上的 o -> a 路径。

Trie 的价值是把“词典维度”压成一棵前缀树。棋盘 DFS 每走一步，就同时知道当前路径是否还是某些单词的前缀；如果不是，直接停止。它不是让 DFS 消失，而是让 DFS 少走大量不可能成功的分支。

words = [oath, oat, oar, eat]

Trie:
root
├─ o ─ a ─ t ─ h
│       └─ r
└─ e ─ a ─ t

棋盘路径走到 o -> b 时，Trie 没有 ob 前缀，立刻剪枝。

二、Trie 在 DFS 中扮演什么角色

普通 DFS 只知道当前路径字符串，比如 "oa"，还要去判断它是不是某个单词前缀。Trie 把这个判断变成节点跳转：当前 DFS 带着一个 Trie 节点，下一格字符能否继续匹配，只看 node.children[ch] 是否存在。

这样避免了反复拼接字符串和遍历词典。更重要的是，Trie 节点把“当前路径对应的词典状态”保存下来，DFS 往下走时状态也同步向下走。棋盘位置负责空间移动，Trie 节点负责词典匹配，两者同时推进。

维度	棋盘 DFS	Trie
状态	当前格子 `(r,c)`	当前前缀节点
扩展	上下左右相邻格	当前字符对应孩子
剪枝	越界、访问过	不存在该前缀
命中	路径形成单词	`word != null` 或 `isEnd=true`

三、用具体棋盘走一遍

设棋盘如下，词典为 ["oath","pea","eat","rain"]。从左上角 o 开始，Trie 有 o 分支，所以继续；走到相邻 a，仍有 oa 前缀；再走到 t、h，命中 oath。

board:
o a a n
e t a e
i h k r
i f l v

path:
(0,0) o -> (0,1) a -> (1,1) t -> (2,1) h
Trie path:
root -> o -> a -> t -> h(isEnd)

若从 p 开头的单词 pea，棋盘中没有 p，从任意格出发第一步都无法走到 Trie 的 p 分支，直接跳过。这就是 Trie 剪枝的直观收益。

四、访问标记和回溯为什么必须恢复

同一个单词路径中不能重复使用同一个格子，所以 DFS 进入格子后要标记访问过。常见做法是把 board[r][c] 暂时改成 '#'，递归结束后恢复原字符。恢复是回溯的关键，因为这个格子可能还要被其他路径使用。

char old = board[r][c];
board[r][c] = '#';
// explore neighbors
board[r][c] = old;

如果不恢复，后续从别的起点出发会误以为该格子不可用，导致漏答案。如果不用原地标记，也可以用 boolean[][] visited，空间是 O(R*C)，逻辑更直观但代码稍长。

五、去重和剪枝优化

同一个单词可能从棋盘不同路径找到，也可能 DFS 多次走到同一个终止节点。常见去重方式是用 Set<String> 保存答案；更高效的方式是命中后把 Trie 节点的 word 置为 null，表示这个词已经收集过。

if (next.word != null) {
    ans.add(next.word);
    next.word = null; // 防止重复加入
}

还可以在某个 Trie 子树已经没有剩余单词时做物理剪枝，把空孩子移除。这个优化能减少后续 DFS 的分支，但实现复杂度更高。面试里先写正确的 Trie + DFS + 去重，再谈剪枝优化即可。

常见误区与追问

记忆钩子：棋盘负责走路，Trie 负责告诉你这条路还有没有词典前缀。

这一节面试官常用来区分“会背 Trie”还是“会把 Trie 放进搜索状态”。回答时要把 2 个剪枝讲清楚：棋盘层面的越界、重复访问剪枝，以及词典层面的前缀不存在剪枝；两者同时成立，复杂度才会比逐词 DFS 明显下降。

误区：对每个单词单独 DFS 就足够了。 单词多且共享前缀时会重复探索，Trie 能合并前缀并剪枝。
误区：DFS 过程中只要路径在 Trie 中存在就加入答案。 必须走到单词结尾节点，前缀本身不一定是完整单词。
误区：访问标记不用恢复。 不恢复会影响其他搜索路径，导致漏解。
追问：为什么命中后可以把 word 置 null？ 这个终止节点对应的单词已加入答案，置空能防重复，不影响更长子路径。
追问：复杂度怎么表达？ 最坏仍可能很高，但 Trie 剪掉不存在前缀的分支，实际远小于逐词 DFS。
追问：能不能只用哈希表存 words？ 哈希表能判断完整单词，但无法高效判断“当前路径是否仍是某些单词前缀”。

加强记忆

单词搜索 II 的核心是把两个搜索空间同步起来：棋盘 DFS 负责枚举相邻格形成的路径，Trie 负责判断当前路径是不是词典前缀。每走一个字符，就从 Trie 当前节点走到对应孩子；走不通立刻剪枝，走到终止节点就收集答案。记忆时抓住“三件套”：词典先建 Trie，棋盘 DFS 带 Trie 节点，访问标记必须回溯恢复。这样就能把暴力逐词搜索改造成共享前缀的一次整体搜索。

简化版

详细版