企业官网建设流程全解析

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。

具体分解为三步：

1. 枚举起点：单词的第一个字母可能落在网格的任何位置，因此对每个单元格都尝试一次以它为首字符的深度优先搜索；
2. 四方向递归：每次匹配成功当前字母后，向「上、右、下、左」四个方向继续匹配单词的下一个字母；
3. 防重复使用：用一张与网格同尺寸的visited布尔矩阵记录当前搜索路径上已占用的单元格，进入子搜索前标记、返回后撤销（回溯），保证「同一次单词路径中同一格只算一次」。

完整 Go 实现

题解文档附带的完整解法与仓库源码 79. Word Search.go 一致，共由一个包级方向常量与三个函数构成。下面按函数逐一结合源码展开。

方向向量dir

var 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]一行即可得到邻居坐标，避免把方向硬编码进递归逻辑。

入口函数exist

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 }

见 79. Word Search.go#L10-L23，两个要点：

• visited矩阵的构建：board是[][]byte，Go 不支持直接对二维切片做make([][]bool, m, n)，因此先make([][]bool, len(board))建立外层，再逐行make([]bool, len(board[0]))填充内层。这张矩阵在所有起点之间共享，但不会造成错误——因为每次searchWord返回时都会把自己的标记撤销干净，搜索失败后矩阵恢复全false，可以安全地用于下一个起点的搜索；
• 起点枚举 + 短路返回：双层for遍历所有单元格作为起点，任一searchWord返回true立即向上短路返回，无需继续尝试其余起点。

边界判断isInBoard

func 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]的访问始终合法。

递归核心searchWord

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 }

见 79. Word Search.go#L29-L45，这是回溯法的完整模板，逐行拆解如下：

这里值得强调回溯的对称性：visited[x][y] = true与visited[x][y] = false恰好一一对应，且false撤销语句位于if块内部、return false之前。这意味着只有「当前格字母匹配成功并进入了子搜索」的路径才会执行撤销；字母不匹配的调用根本不触碰visited，状态天然保持干净。这种「标记—探索—撤销」三段式正是 LeetCode-Go 仓库中网格回溯类题解的通用结构。

运行流程：以示例 "ABCCED" 走查

以文档给出的3×4示例网格匹配"ABCCED"为例，说明实际执行路径：

1. 外层枚举从(0,0)='A'开始，searchWord匹配成功并标记visited[0][0]；
2. 向右走到(0,1)='B'成功，继续向右(0,2)='C'成功；
3. 在(0,2)处向四个方向展开：下邻(1,2)='C'命中第 4 个字母，继续；
4. (1,2)的右邻(1,3)='S'、下邻(2,2)='E'中，'E'命中第 5 个字母；
5. 在(2,2)处index == len(word)-1，判断board[2][2]=='D'？不成立，回溯；换左邻(2,3)='E'同样失败，逐层撤销标记返回false；
6. 外层继续枚举其余起点……实际上第一条路径在步骤 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 [][]byte+word string）与ans79（期望结果one bool）两个结构体，并在Test_Problem79中用question79切片批量驱动，见 79. Word Search_test.go#L8-L11 与 79. Word Search_test.go#L26-L104。

测试数据共 7 组，覆盖了两类网格：

这套用例设计值得注意：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 -covermode=atomic -coverprofile=coverage.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) 调用栈空间。

可复用的实现要点小结

从本仓库这道题解中可以沉淀出网格搜索类问题的通用模式：

1. 方向常量外置：dir [][]int包级定义，四方向展开一行搞定，方便迁移到八方向（扩展dir）或特殊走法问题；
2. 终止条件落在「最后一个字母」上：index == len(word)-1时比较当前格而非递归，天然兼容长度 1 的单词；
3. 标记与撤销严格对称：visited的置位与复位一一对应，且只在字母匹配成功的路径上操作，使多起点共享同一张visited成为可能；
4. 短路返回贯穿全链路：递归命中即逐级return true，外层起点枚举也随之短路，避免无谓搜索。

相关文件索引

• 英文题解文档（本篇主体依据）：website/content.en/ChapterFour/0001~0099/0079.Word-Search.md
• 中文题目与思路说明：leetcode/0079.Word-Search/README.md
• Go 解法源码：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-Go）：go.mod

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go