LeetCode-Go 题解 79. Word Search用回溯法在二维网格中搜索单词的 Go 实现与源码剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本篇基于 LeetCode-Go 仓库中第 79 题 Word Search 的官方题解文档完整讲解「二维网格单词搜索」问题的回溯DFS解法从问题定义、四方向搜索的递归设计到 Go 实现中visited标记矩阵、边界判断与回溯撤销的源码级细节并对照仓库测试用例说明如何验证解法正确性。读完后你将掌握该题的标准 DFS 回溯模板并能直接复用到同类网格路径搜索问题中。问题定义原题英文题解文档给出的英文描述如下Given a 2D board and a word, find if the word exists in the grid.The word can be constructed from letters of sequentially adjacent cell, where adjacent cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.即给定一个二维字符网格和一个单词判断该单词是否存在于网格中。单词必须由顺序相邻的单元格字母构成「相邻」指水平或垂直方向上的邻居不含对角线且同一个单元格只能被使用一次。题目给出的标准示例该示例同时出现在题解文档、中文 README 与测试文件中board [ [A,B,C,E], [S,F,C,S], [A,D,E,E] ] Given word ABCCED, return true. Given word SEE, return true. Given word ABCB, return false.其中ABCB返回false正是「同一单元格不能重复使用」这一约束的直接体现从右上角的B出发走到左下角的B后已无法再复用起点那个B作为最后一个字母。解题思路四方向 DFS 搜索题解文档给出的核心思路只有一句话但信息量足够从网格中的任意一个点出发向 4 个方向分别进行 DFS 搜索直到单词的所有字母都找到就返回true否则返回false。具体分解为三步枚举起点单词的第一个字母可能落在网格的任何位置因此对每个单元格都尝试一次以它为首字符的深度优先搜索四方向递归每次匹配成功当前字母后向「上、右、下、左」四个方向继续匹配单词的下一个字母防重复使用用一张与网格同尺寸的visited布尔矩阵记录当前搜索路径上已占用的单元格进入子搜索前标记、返回后撤销回溯保证「同一次单词路径中同一格只算一次」。完整 Go 实现题解文档附带的完整解法与仓库源码 79. Word Search.go 一致共由一个包级方向常量与三个函数构成。下面按函数逐一结合源码展开。方向向量dirvar dir [][]int{ {-1, 0}, // 上 {0, 1}, // 右 {1, 0}, // 下 {0, -1}, // 左 }见 79. Word Search.go#L3-L8。四个偏移量对应「上、右、下、左」四个方向是网格四方向搜索的惯用写法。将其定义为包级常量后递归函数中只需nx : x dir[i][0]、ny : y dir[i][1]一行即可得到邻居坐标避免把方向硬编码进递归逻辑。入口函数existfunc 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 }见 79. Word Search.go#L10-L23两个要点visited矩阵的构建board是[][]byteGo 不支持直接对二维切片做make([][]bool, m, n)因此先make([][]bool, len(board))建立外层再逐行make([]bool, len(board[0]))填充内层。这张矩阵在所有起点之间共享但不会造成错误——因为每次searchWord返回时都会把自己的标记撤销干净搜索失败后矩阵恢复全false可以安全地用于下一个起点的搜索起点枚举 短路返回双层for遍历所有单元格作为起点任一searchWord返回true立即向上短路返回无需继续尝试其余起点。边界判断isInBoardfunc isInBoard(board [][]byte, x, y int) bool { return x 0 x len(board) y 0 y len(board[0]) }见 79. Word Search.go#L25-L27。对(x, y)做上下界检查x的行范围取len(board)y的列范围取len(board[0])。在递归展开邻居前调用它保证searchWord内部对board[x][y]的访问始终合法。递归核心searchWordfunc 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 }见 79. Word Search.go#L29-L45这是回溯法的完整模板逐行拆解如下代码位置作用if index len(word)-1 { return board[x][y] word[index] }递归终止条件index已指向单词最后一个字母此时只需判断当前格字母是否等于它而不是返回true或继续递归。这一写法同时兼容「单词长度可能为 1」的边界情况if board[x][y] word[index]首字符剪枝当前格字母与期望字母不匹配时直接失败返回不进入递归、不做任何标记visited[x][y] true进入当前格的搜索路径先占位防止四条方向的递归回头占用本格for i : 0; i 4; i按dir展开四个方向的邻居(nx, ny)isInBoard(...) !visited[nx][ny] searchWord(..., index1, nx, ny)三个条件依次是邻居在网格内、邻居未被本路径占用、下一字母递归匹配成功。任一为true即整体返回true短路visited[x][y] false回溯撤销四条方向全部尝试完仍未命中说明本路径走不通撤销标记后返回false让其他起点或其他分支可以重新使用这个格子这里值得强调回溯的对称性visited[x][y] true与visited[x][y] false恰好一一对应且false撤销语句位于if块内部、return false之前。这意味着只有「当前格字母匹配成功并进入了子搜索」的路径才会执行撤销字母不匹配的调用根本不触碰visited状态天然保持干净。这种「标记—探索—撤销」三段式正是 LeetCode-Go 仓库中网格回溯类题解的通用结构。运行流程以示例 ABCCED 走查以文档给出的3×4示例网格匹配ABCCED为例说明实际执行路径外层枚举从(0,0)A开始searchWord匹配成功并标记visited[0][0]向右走到(0,1)B成功继续向右(0,2)C成功在(0,2)处向四个方向展开下邻(1,2)C命中第 4 个字母继续(1,2)的右邻(1,3)S、下邻(2,2)E中E命中第 5 个字母在(2,2)处index len(word)-1判断board[2][2]D不成立回溯换左邻(2,3)E同样失败逐层撤销标记返回false外层继续枚举其余起点……实际上第一条路径在步骤 3 之后应继续尝试其他方向ABCCED的合法路径是A(0,0)→B(0,1)→C(0,2)→C(1,2)→E(2,2)→D(2,3)并不存在E在(2,2)D在其左正确路径为A(0,0)→B(0,1)→C(0,2)→C(1,2)→E(1,3)也不成立。实际命中路径是A(0,0)→B(0,1)→C(0,2)→C(1,2)→E(2,2)→D失败后回溯换路A(0,0)→B(0,1)→C(0,2)→E(0,3)→...。题解文档断言该用例返回true对应的命中路径为A(0,0)→B(0,1)→C(0,2)→C(1,2)→E(2,2)无法闭合时的另一分支C(1,2)→E(2,2)走不通最终由C(0,2)的右邻分支闭合——具体哪条分支命中不影响结论DFS 的穷举保证只要存在合法路径就一定能被找到而visited撤销保证搜索空间不被污染。需要说明的是上面的逐步走查是对「DFS 穷举 回溯」行为的描述性还原从源码结构看searchWord并不记录路径本身只负责返回布尔结果因此文章不逐帧断言唯一命中分支读者可运行测试自行观察见下一节。测试用例与验证方式仓库在 79. Word Search_test.go 中为该题组织了结构化测试数据。其模式是定义para79参数b [][]byteword string与ans79期望结果one bool两个结构体并在Test_Problem79中用question79切片批量驱动见 79. Word Search_test.go#L8-L11 与 79. Word Search_test.go#L26-L104。测试数据共 7 组覆盖了两类网格网格单词期望考察点ABC E / S F C S / A D E EABCCEDtrue文档主示例的正向路径同上SEEtrue短单词的命中同上ABCBfalse同格不可复用的负向约束o a a n / e t a e / i h k r / i f l voathtrue4×4 网格上的长路径同上peafalse字母齐全但排列不合法的负向用例同上eattrue同一网格的第二条合法路径同上rainfalse另一条不合法路径这套用例设计值得注意pea、eat、rain三组共享同一网格专门验证 DFS 在「字母都存在但相邻关系不成立」时不会误报true同时oath验证了路径可以绕行长距离。测试末尾通过fmt.Printf打印每组输入与exist(p.b, p.word)的实时输出便于人工核对见 79. Word Search_test.go#L98-L104。在仓库根目录验证该题解法可直接运行go test -v -run Test_Problem79 ./leetcode/0079.Word-Search/仓库整体则通过 gotest.sh 对全部leetcode/...包做原子模式覆盖率统计go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本Go 1.10 特性一次性生成单个合法的coverage.txt对应仓库根目录已有的 coverage.txt 产物与项目「100% 测试覆盖」的定位一致。复杂度分析设网格为m×n单词长度为L时间复杂度最坏情况下对每个单元格m·n个都启动一次 DFS每条路径在最多 4 个方向上展开、深度为L即 O(m·n·4^L)。实际执行中board[x][y] word[index]的首字符剪枝与visited占用检查会大幅削减可展开的分支因此实测开销远低于该上界空间复杂度visited矩阵占用 O(m·n)递归栈深度不超过单词长度 L另需 O(L) 调用栈空间。可复用的实现要点小结从本仓库这道题解中可以沉淀出网格搜索类问题的通用模式方向常量外置dir [][]int包级定义四方向展开一行搞定方便迁移到八方向扩展dir或特殊走法问题终止条件落在「最后一个字母」上index len(word)-1时比较当前格而非递归天然兼容长度 1 的单词标记与撤销严格对称visited的置位与复位一一对应且只在字母匹配成功的路径上操作使多起点共享同一张visited成为可能短路返回贯穿全链路递归命中即逐级return true外层起点枚举也随之短路避免无谓搜索。相关文件索引英文题解文档本篇主体依据website/content.en/ChapterFour/0001~0099/0079.Word-Search.md中文题目与思路说明leetcode/0079.Word-Search/README.mdGo 解法源码leetcode/0079.Word-Search/79. Word Search.go测试用例文件leetcode/0079.Word-Search/79. Word Search_test.go全量覆盖率脚本gotest.sh模块定义go 1.19模块名github.com/halfrost/LeetCode-Gogo.mod【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考