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 212Word 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-zwords中的单词互不重复。题目大意在一个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, index1, nx, ny) { return true } } visited[x][y] false } return false }searchWord是核心回溯函数终止条件当index len(word)-1时只需判断当前格子字母是否等于单词最后一个字母匹配分支若当前格子字母与word[index]相等先置visited[x][y] true防止本路径回头再向四个方向递归寻找index1回溯还原四个方向都失败时执行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.goTrie 参考实现见 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），仅供参考
LeetCode-Go 题解：212. Word Search II —— 从朴素 DFS 到 Trie 前缀树优化
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 212Word 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-zwords中的单词互不重复。题目大意在一个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, index1, nx, ny) { return true } } visited[x][y] false } return false }searchWord是核心回溯函数终止条件当index len(word)-1时只需判断当前格子字母是否等于单词最后一个字母匹配分支若当前格子字母与word[index]相等先置visited[x][y] true防止本路径回头再向四个方向递归寻找index1回溯还原四个方向都失败时执行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.goTrie 参考实现见 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），仅供参考
