LeetCode-Go 题解：212. Word Search II —— 从朴素 DFS 到 Trie 前缀树优化
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
导读
本文以 LeetCode 212（Word Search II）为核心，讲解如何在二维字符网格中同时查找字典中的多个单词。题目本身是 79. Word Search 的加强版，本仓库给出了基于 79 题exist函数逐词 DFS 的朴素实现（见 leetcode/0212.Word-Search-II/212. Word Search II.go），并以测试用例验证了正确性。读完本文，你将掌握：题目约束与复杂度分析、仓库内朴素实现的逐行拆解、以及如何借助前缀树（Trie，参见 leetcode/0208.Implement-Trie-Prefix-Tree.go) 的实现模式）把多个单词的搜索合并为一次共享前缀的深度优先遍历，大幅降低时间复杂度。
题目描述与约束
给定一个二维字符网格board和一个字典单词列表words，找出所有同时出现在二维网格和字典中的单词。
单词必须按照字母顺序，由水平相邻或垂直相邻的单元格中的字母依次构成；同一个单元格内的字母在一个单词中不允许被重复使用（即一个单词的搜索路径不能自交）。
示例：
Input: board = [ ['o','a','a','n'], ['e','t','a','e'], ['i','h','k','r'], ['i','f','l','v'] ] words = ["oath","pea","eat","rain"] Output: ["eat","oath"]约束条件：
- 所有输入只包含小写字母
a-z； words中的单词互不重复。
题目大意
在一个m × n的网格与一个字典之间求交集：网格中可以按相邻关系"拼"出来的单词，且该单词同时出现在words列表中，就输出它。示例中"oath"与"eat"都能在网格中拼出且出现在字典里，而"pea"、"rain"无法在网格中完整拼出，故被排除。
解题思路：基于 79 题的朴素 DFS
为什么说它是 79 题的加强版
- Word Search 只判断单个单词是否存在于网格中；而 212 题把输入从单个字符串扩展成字符串数组
words，要求一次性返回所有能被拼出的单词。
仓库文档在 212. Word Search II 题解 中明确指出：思路仍然可以照搬 79 题的 DFS 搜索，但时间复杂度特别高——若words共有k个单词，每个单词都独立地在整个网格上跑一遍 DFS，总开销约为k倍的单次搜索开销，网格大、单词多时会非常昂贵。因此文档以"想想更优的解法"收尾，指向下文的前缀树优化。
仓库内朴素实现的完整拆解
本仓库在 212. Word Search II.go 中给出了"逐词复用 79 题exist"的实现，代码结构如下：
func findWords(board [][]byte, words []string) []string { res := []string{} for _, v := range words { if exist(board, v) { res = append(res, v) } } return res }findWords对字典中的每个单词依次调用exist，命中就追加到结果切片res。由于words值互异（题目 Note 保证），结果天然不会重复。
// these is 79 solution var dir = [][]int{ {-1, 0}, {0, 1}, {1, 0}, {0, -1}, }dir定义四个搜索方向：上、右、下、左。每个方向的偏移量恰好对应网格坐标系中(x, y)的四个邻居。
func exist(board [][]byte, word string) bool { visited := make([][]bool, len(board)) for i := 0; i < len(visited); i++ { visited[i] = make([]bool, len(board[0])) } for i, v := range board { for j := range v { if searchWord(board, visited, word, 0, i, j) { return true } } } return false }exist负责两件事：一是初始化与网格同尺寸的visited布尔矩阵，标记"当前单词的搜索路径上哪些格子已被占用"，从而满足"同一个字母单元格在一个单词中不允许重复使用"的约束；二是以网格中每个格子为起点调用searchWord，只要任一位置能拼出完整单词就返回true。
func isInBoard(board [][]byte, x, y int) bool { return x >= 0 && x < len(board) && y >= 0 && y < len(board[0]) } func searchWord(board [][]byte, visited [][]bool, word string, index, x, y int) bool { if index == len(word)-1 { return board[x][y] == word[index] } if board[x][y] == word[index] { visited[x][y] = true for i := 0; i < 4; i++ { nx := x + dir[i][0] ny := y + dir[i][1] if isInBoard(board, nx, ny) && !visited[nx][ny] && searchWord(board, visited, word, index+1, nx, ny) { return true } } visited[x][y] = false } return false }searchWord是核心回溯函数：
- 终止条件：当
index == len(word)-1时，只需判断当前格子字母是否等于单词最后一个字母； - 匹配分支：若当前格子字母与
word[index]相等，先置visited[x][y] = true防止本路径回头，再向四个方向递归寻找index+1； - 回溯还原：四个方向都失败时执行
visited[x][y] = false，把格子"释放"给其他起点或方向使用； - 越界与占用检查：递归前用
isInBoard保证坐标合法，用!visited[nx][ny]保证不重复使用格子。
朴素实现的复杂度
设网格为m × n，单词平均长度为L，单词个数为k：
- 时间复杂度：约
O(k · m · n · 4^L)。每个单词都要独立从所有格子出发做回溯搜索，分支因子最大为 4； - 空间复杂度：
O(m · n)（visited矩阵）加上递归栈深度O(L)。
这就是文档强调"时间复杂度特别高"的原因：k个单词存在大量共享前缀，朴素实现却把相同前缀的探索重复执行了k次。
测试用例验证
仓库在 212. Word Search II_test.go 中覆盖了两个场景：
- 79 题经典网格
[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]配合["ABCCED","SEE","ABCB"]，期望输出["ABCCED","SEE"]——验证了ABCB虽然能部分拼出，但最终无法走通，证明回溯逻辑正确； - 本题示例网格
[["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]]配合["oath","pea","eat","rain"]，期望输出["oath","eat"]。
更优解法：Trie + 深度优先搜索
文档末尾提示"想想更优的解法"，标准答案是用前缀树（Trie）合并所有单词的前缀，再在网格上做一次共享的 DFS。本仓库虽未对 212 单独实现该方案，但提供了可直接参考的 Trie 数据结构的 Go 实现，见 leetcode/0208.Implement-Trie-Prefix-Tree/208. Implement Trie (Prefix Tree).go.go)：
type Trie struct { isWord bool children map[rune]*Trie }其核心思想是：
- 每个节点
children存储以该节点为前缀的下一字符映射，isWord标记是否存在以该节点结尾的完整单词； Insert沿字符逐层建链，并在终点置isWord = true（对应208题解 208. Implement Trie (Prefix Tree).go.go#L14-L26)）；Search/StartsWith沿前缀逐层查询（208. Implement Trie (Prefix Tree).go.go#L29-L52)），后者正是 DFS 剪枝所需要的"该前缀是否还有单词可拼"判断。
Trie 化的解题流程
- 用
words中所有单词构建一棵 Trie； - 从网格中每个格子出发做 DFS，同时维护"当前节点在 Trie 中的位置"；
- 剪枝：若当前 Trie 节点下不存在任何单词以当前路径为前缀（等价于
StartsWith失败），立即终止该路径，不再继续四方向探索； - 收集结果：当 DFS 到达某个
isWord == true的节点时，记录该单词，并将该节点的isWord置为false防止重复输出； - 沿用 79 题的
visited回溯机制保证一个单词的路径不重复使用格子。
为什么 Trie 方案更快
朴素实现中，["oath","oats","oak"]这类共享"oa"前缀的单词会在网格上重复搜索"oa"三次；Trie 方案把前缀合并为一棵字典树，一次 DFS 同时覆盖所有以该前缀开头的单词，只有当路径前缀在 Trie 中"无后继"时才剪枝。整体复杂度从O(k · m · n · 4^L)降为约O(m · n · 4^L)（L为最长匹配路径长度），空间上以 Trie 的存储换取搜索次数的减少。
与 208 题 Trie 的衔接要点
若基于本仓库的 Trie 实现改造，需要注意两点：其一，208的 Trie 用map[rune]*Trie存储子节点，DFS 中可通过children[rune(board[x][y])]在O(1)时间内判断"下一格字母是否是合法后继"；其二，DFS 递归参数需要同时携带当前 Trie 节点指针与当前拼出的字符串（或在节点上记录单词），到达isWord节点时即可输出。实际应用中还可将网格改为原地标记（如把已访问格子字符临时改为'#'）以省去visited矩阵，属于实现层面的进一步优化。
小结
- 朴素实现：复用 79. Word Search 的
exist逐词 DFS，正确但时间复杂度高，适合理解回溯本质； - 进阶思路：用 Trie 合并
words前缀、DFS 共享搜索并剪枝，是本题的工业级解法，也是文档"想想更优的解法"指向的方向； - 仓库证据链：完整实现见 212. Word Search II.go，测试见 212. Word Search II_test.go，Trie 参考实现见 208. Implement Trie (Prefix Tree).go.go)。
从"一个单词"（79）到"一批单词"（212），再到"前缀合并共享搜索"，这条演化路径既是面试高频考点，也是把回溯、剪枝与字典树三类基本功融会贯通的绝佳练习。
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
