单词搜索 II 为什么要用 Trie + 回溯？如何剪枝避免逐词 DFS？

简化版

单词搜索 II 不适合对每个单词单独 DFS。更优做法是先把 words 建成 Trie，然后从棋盘每个格子出发回溯，同时沿 Trie 前缀往下走；如果当前字符在 Trie 中没有对应孩子，立即剪枝。走到 Trie 单词结尾就收集答案，并继续搜索更长单词。

详细版

暴力做法是对每个单词都在棋盘上跑一次 Word Search，复杂度接近 wordsCount * m * n * 4^L，大量共享前缀会被重复搜索。Trie 可以把词典的公共前缀合并，例如 oath 和 oat 共享 o -> a -> t。

回溯时状态包含棋盘坐标 (r,c)、当前 Trie 节点和访问标记。进入格子前先检查当前字符是否是 Trie 当前节点的孩子；不是就返回。是的话移动到孩子节点，若该节点保存了完整单词，就加入结果。随后向上下左右继续搜索，过程中要标记当前格已访问，返回时恢复。

为了避免重复答案，可以在命中后把节点上的 word 置空。进一步优化还可以在某个 Trie 子树已经没有孩子时从父节点删除，减少后续搜索。

完整版教学

一、为什么逐词 DFS 会浪费

Word Search I 是给一个单词，判断棋盘里是否存在路径。Word Search II 是给一批单词，找出所有存在的单词。如果对每个单词都单独搜索，棋盘会被反复遍历，同样的前缀也会被反复验证。

例如单词 ["oat","oath","oats"] 都共享前缀 o -> a -> t。逐词 DFS 会为这三个单词分别搜索 oat 前缀；Trie + 回溯只搜索一次前缀路径，到达不同终止节点时收集不同单词。

Trie:
root
 └─ o
    └─ a
       └─ t (oat)
          ├─ h (oath)
          └─ s (oats)

二、Trie 在回溯里承担什么角色

Trie 不是为了替代 DFS，而是为了告诉 DFS “当前路径是否仍可能成为某个单词”。棋盘 DFS 负责枚举相邻格路径，Trie 负责做前缀合法性检查。两者同步推进，才能尽早剪掉无效分支。

如果当前路径是 "ox"，而词典里没有任何单词以 "ox" 开头，那么无论后面再接多少格都不可能命中，可以立刻返回。这个剪枝比等到路径长度达到某个单词长度再判断高效得多。

记忆钩子：棋盘负责“往哪里走”，Trie 负责“这条路还有没有词典前缀价值”。

三、回溯状态和访问标记

递归状态通常是 (r, c, trieNode)。trieNode 表示当前路径已经匹配到 Trie 的哪个节点；进入 (r,c) 时，用 board[r][c] 去找 trieNode.children[ch]。找不到就剪枝，找得到才继续。

访问标记是本题的另一个关键：同一个单词路径中，一个格子不能重复使用。因此进入格子后要临时标记，如把 board[r][c] 改成 '#'；递归搜索四邻后必须恢复原字符。

进入格子 -> 检查 Trie 孩子 -> 标记已访问
        -> 收集 word -> 搜索四邻
        -> 恢复棋盘字符

这个恢复动作就是回溯。如果忘记恢复，后续从其它起点出发会误以为该格不可用。

四、代码模板

Trie 节点可以保存 children 和 word。当 word != null 时，说明从根到当前节点形成一个完整单词。命中后把 word 置空，可以防止同一个单词被不同路径重复加入。

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    String word;
}

List<String> findWords(char[][] board, String[] words) {
    TrieNode root = buildTrie(words);
    List<String> res = new ArrayList<>();
    for (int r = 0; r < board.length; r++) {
        for (int c = 0; c < board[0].length; c++) {
            dfs(board, r, c, root, res);
        }
    }
    return res;
}

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

    if (next.word != null) {
        res.add(next.word);
        next.word = null;
    }

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

这段模板体现了“先用 Trie 剪枝，再标记访问，再搜索四邻，最后恢复”的顺序。

五、用数字例子理解剪枝收益

假设棋盘是 12 个格子、词典有 1000 个单词、平均长度 8。逐词 DFS 粗略上限接近 1000 * 12 * 4^8，前缀重复会非常浪费。Trie + DFS 从每个起点只走词典存在的前缀，很多分支在第 1 到第 3 个字符就被剪掉。

方案	搜索单位	是否共享前缀	典型问题
对每个单词 DFS	单词	否	重复搜索公共前缀
Trie + 棋盘 DFS	前缀路径	是	需要维护 Trie 节点和回溯标记

复杂度理论上仍可能很高，因为棋盘路径数量本身指数级；但 Trie 把“词典不存在的前缀”全部提前砍掉，是本题能通过的关键。

六、常见误区与追问

误区：命中一个单词后立刻停止当前 DFS。 不能停止，因为当前单词可能是更长单词的前缀，如 oat 和 oath。
误区：只用 Set 存 words，不建 Trie。 Set 只能判断完整单词，无法高效判断当前路径是否是合法前缀。
误区：访问标记不恢复。 会污染其它起点或其它分支，导致漏答案。
追问：如何避免重复答案？ 命中后把 Trie 节点的 word 置空，或用 Set 收集结果。
追问：还能继续优化吗？ 可以在子节点无孩子且 word 为空时从父节点删除，动态剪掉已无价值的 Trie 分支。
追问：为什么不从 Trie 单词出发找棋盘路径？ 那会退化成逐词 Word Search，无法共享棋盘上的公共前缀搜索。

七、加强记忆

单词搜索 II 记成“棋盘 DFS 枚举路径，Trie 判断前缀是否值得走”。每走一个格子，就同步走 Trie 的一个孩子；走不通立刻剪枝，走到 word 节点就收集，四邻搜索后恢复访问标记。它的关键不是回溯模板本身，而是把词典前缀剪枝嵌进模板里。

简化版

详细版