基于 Backtracking 的二维网格单词搜索以 leetcode 仓库多语言实现剖析 Word Search 三种解法【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以仓库中 articles/search-for-word.md 为核心骨架结合 python/0079-word-search.py、cpp/0079-word-search.cpp 等 12 种语言源码系统讲解在m × n字符网格中判断给定单词是否可沿上下左右相邻路径构成的问题LeetCode 79. Word Search。读完本文你将掌握三类回溯解法Hash Set、Visited 数组、原地标记、各自的复杂度含义、常见实现陷阱以及仓库源码中体现的工程化优化技巧。问题背景与前置知识题目本质给定一个m × n的字符矩阵board与一个字符串word判断word是否可以通过在网格中沿水平或垂直方向相邻移动、按顺序连接字符而构成。同一个单元格在一条路径中最多只能使用一次。例如对如下网格判断ABCCEDA B C E S F C S A D E E从左上角A出发沿A → B → C → C → E → D即可找到该单词。前置技能清单原文档明确要求读者在动手前掌握以下四个基础这也是本题的解题脚手架Backtracking回溯通过做选择 → 递归 → 撤销选择穷举所有可能路径遇到死路时回退尝试其他分支Depth-First SearchDFS沿一条分支尽可能深入再回溯探索其他分支的图/网格遍历方式2D Grid Traversal二维网格遍历在矩阵中沿四个方向上下左右移动并跟踪已访问单元格防止重复访问Recursion递归理解递归调用与终止条件base case的设计。解法一Backtracking Hash Set核心思路对于网格中的每一个单元格都尝试把它作为单词的起点。若当前单元格字符与word[i]匹配则向四个邻居递归匹配下一个字符在递归过程中把已使用的单元格坐标放入一个Hash SetPython 的set、Java 的HashSet等确保同一条路径内不重复使用某条路径失败后把该坐标从集合中移除撤销再尝试其他方向。只要某一次递归匹配完所有字符立即返回true。算法步骤遍历网格中每个单元格(r, c)从该点启动匹配定义dfs(r, c, i)表示从(r, c)出发、匹配word[i]及之后字符的能力dfs中若i len(word)说明全部字符已匹配 → 返回true若越界、字符不匹配、或(r, c)已在path中 → 返回false将(r, c)加入path向四个邻居递归i 1递归返回后从path中删除(r, c)回溯撤销任一起点返回true则答案为true否则为false。代码实现Python / Cclass Solution: def exist(self, board: List[List[str]], word: str) - bool: ROWS, COLS len(board), len(board[0]) path set() def dfs(r, c, i): if i len(word): return True if (min(r, c) 0 or r ROWS or c COLS or word[i] ! board[r][c] or (r, c) in path): return False path.add((r, c)) res (dfs(r 1, c, i 1) or dfs(r - 1, c, i 1) or dfs(r, c 1, i 1) or dfs(r, c - 1, i 1)) path.remove((r, c)) return res for r in range(ROWS): for c in range(COLS): if dfs(r, c, 0): return True return FalseC 版本在 cpp/0079-word-search.cpp 中采用了先判断首字符再进入 DFS的写法for (int i 0; i m; i) { for (int j 0; j n; j) { if (board[i][j] word[0]) { // 首字符不匹配则跳过 if (dfs(board, word, 0, i, j, m, n)) { return true; } } } }该实现与文档中的 Python 版本互为印证文档版在dfs内部统一做越界/字符/已访问检查C 版则在入口处先过滤掉与word[0]无关的起点本质一致、只是剪枝时机不同。复杂度时间$O(m \times 4^n)$其中 $m$ 为网格单元格总数$n$ 为单词长度最坏情况下每个起点都要沿四个方向探索到单词长度空间$O(n)$即递归栈深度加上路径集合的大小集合中最多同时保存 $n$ 个坐标。解法二Backtracking Visited 数组核心思路思路与解法一完全一致区别在于去重数据结构不使用 Hash Set而是维护一个与网格同尺寸的visited布尔矩阵。visited[r][c] true表示该单元格已属于当前路径递归时直接剪枝回溯时将标志复位为false。算法步骤创建与 board 同尺寸的visited矩阵初始全为false遍历每个单元格(r, c)启动dfs(r, c, 0)dfs中i len(word)返回true越界、字符不匹配或visited[r][c]为真则返回false标记visited[r][c] true→ 递归四邻居i 1→ 复位visited[r][c] false任一调用返回true即整体为true。代码实现Python / Goclass Solution: def exist(self, board: List[List[str]], word: str) - bool: ROWS, COLS len(board), len(board[0]) visited [[False for _ in range(COLS)] for _ in range(ROWS)] def dfs(r, c, i): if i len(word): return True if (r 0 or c 0 or r ROWS or c COLS or word[i] ! board[r][c] or visited[r][c]): return False visited[r][c] True res (dfs(r 1, c, i 1) or dfs(r - 1, c, i 1) or dfs(r, c 1, i 1) or dfs(r, c - 1, i 1)) visited[r][c] False return res for r in range(ROWS): for c in range(COLS): if dfs(r, c, 0): return True return FalseGo 版本go/0079-word-search.go在标记前先保存原值、用临时变量tmp配合visited矩阵完成标记 → 递归 → 还原的完整闭环tmp : board[i][j] board[i][j] * res : dfs(i1, j, curr1) || dfs(i-1, j, curr1) || dfs(i, j-1, curr1) || dfs(i, j1, curr1) board[i][j] tmp复杂度时间$O(m \times 4^n)$空间$O(n)$递归栈深度visited矩阵作为辅助数据一般记为 $O(m \times n)$但因为每个单元格只会在单一路径中被标记与路径长度相关的有效占用为 $O(n)$文档将其记为 $O(n)$。解法三Backtracking 原地标记Optimal核心思路前两种解法都需要额外的数据结构记录路径占用。最优解法省去额外空间在递归进入某单元格时直接把board[r][c]临时改写为特殊占位符#仓库部分实现用*如 typescript/0079-word-search.ts 与 javascript/0079-word-search.js从而递归中一旦读到#即可判定该单元格已在当前路径中不可复用四方向探索完毕后把原字符恢复回溯供其他起点复用。算法步骤定义dfs(r, c, i)能否从(r, c)匹配word[i...]终止i len(word)→true失败越界、board[r][c] ! word[i]、或board[r][c] #→false标记board[r][c] #向四方向递归i 1还原board[r][c] word[i]从每个单元格执行dfs(r, c, 0)任一为true即整体为true。代码实现Python / Javaclass Solution: def exist(self, board: List[List[str]], word: str) - bool: ROWS, COLS len(board), len(board[0]) def dfs(r, c, i): if i len(word): return True if (r 0 or c 0 or r ROWS or c COLS or word[i] ! board[r][c] or board[r][c] #): return False board[r][c] # res (dfs(r 1, c, i 1) or dfs(r - 1, c, i 1) or dfs(r, c 1, i 1) or dfs(r, c - 1, i 1)) board[r][c] word[i] return res for r in range(ROWS): for c in range(COLS): if dfs(r, c, 0): return True return FalseJava 版本java/0079-word-search.java提供了一个有趣的变体不写死#而是利用 ASCII 溢出特性——board[i][j] 100把字母偏移成非字母字符递归返回后再board[i][j] - 100还原。其注释说明了设计动机I added 100 because it will exceed the ascii limit for characters and will change it to some ascii value which is not an alphabet.加 100 会超出 ASCII 字母范围变成非字母值从而天然成为已访问标记。这说明占位符的具体取值并不重要重要的是改值标记 还原回溯这一机制。复杂度时间$O(m \times 4^n)$空间$O(n)$且去掉了 Hash Set / visited 数组的额外开销这是它被称为 Optimal 的原因。三种解法的对比与选择维度解法一 Hash Set解法二 Visited 数组解法三 原地标记去重方式坐标集合布尔矩阵改写单元格为#/*额外空间$O(n)$ 集合$O(m \times n)$ 矩阵路径内有效占用 $O(n)$无是否修改入参否否是需还原适用场景思路直观、易理解常规竞赛首选面试/生产中最省内存三者的递归框架完全相同区别仅在于路径占用如何记录与撤销这也是回溯问题中状态管理这一核心思想的三种典型体现。仓库中 python/0079-word-search.py、rust/0079-word-search.rs 使用 Hash Set / visited 矩阵cpp/0079-word-search.cpp、typescript/0079-word-search.ts、javascript/0079-word-search.js、go/0079-word-search.go 则使用原地标记恰好覆盖了三种策略的工程实践。常见陷阱Common Pitfalls原文档在末尾集中总结了回溯实现中最容易出错的三类问题这些同样是仓库多语言实现中反复出现的注意点1. 回溯后忘记还原单元格用改值法#/*标记已访问时如果探索完四方向后没有把原字符写回board 将被永久修改。后续从其他起点发起的路径会把本可用的单元格误判为已访问导致漏解。正确做法是如 TypeScript 版所示进入时保存currentCell返回前board[row][col] currentCell复位。2. 已访问检查与字符匹配检查的顺序若单元格被改写成#board[r][c] ! word[i]会天然失败因此顺序问题不明显但使用独立 visited 结构时先查 visited 再查字符匹配的顺序会影响正确性与可读性。文档建议将越界、字符匹配、已访问三项检查统一放在递归入口处一次性短路判定避免在分支逻辑中分散处理。3. 未匹配首字符就盲目启动 DFS从每个单元格直接启动dfs(r, c, 0)虽然逻辑正确但会浪费大量算力在首字符都不匹配的起点上。在 board 较大时先判断board[r][c] word[0]再递归能显著剪枝——这正是 cpp/0079-word-search.cpp 在入口双重循环里做的事。仓库源码中的进阶优化除了文档所述三种解法仓库中的实现还体现了若干值得借鉴的工程化优化可作为深入学习的延伸字符频次预检与单词反转python/0079-word-search.py 在 DFS 前统计了 board 中所有字符的频次# To prevent TLE, reverse the word if frequency of the first letter is more than the last letters count sum(map(Counter, board), Counter()) if count[word[0]] count[word[-1]]: word word[::-1]其原理是优先从出现频率更低的字符开始搜索可大幅减少起点分支数是应对超时TLE的有效剪枝。Rust 的位运算编码优化rust/0079-word-search.rs 把字符编码为 6 位数值encode将A-Z映射为 1–26将整个单词压缩进一个u128整数配合word 6逐位比对并增加两项前置检查board.len() * board[0].len() word.len()网格容量不足时直接返回false频次计数器出现负值word 中存在 board 中没有的字符时直接返回false。这些先证伪再搜索的策略是大型网格下避免无效递归的经典手法。仓库中的多语言实现与相关题目本仓库在 12 种语言目录下均提供了本题的完整实现路径规律为语言目录/0079-word-search.扩展名语言文件Pythonpython/0079-word-search.pyCcpp/0079-word-search.cppJavajava/0079-word-search.javaJavaScriptjavascript/0079-word-search.jsTypeScripttypescript/0079-word-search.tsGogo/0079-word-search.goRustrust/0079-word-search.rsCc/0079-word-search.cC# / Kotlin / Swift / Ruby对应目录下的同名文件此外本题的进阶版本是Word Search IILeetCode 212需要借助 Trie 同时搜索多个单词仓库同样提供了0079/0212两个题号的完整多语言实现如 python/0212-word-search-ii.py、cpp/0212-word-search-ii.cpp可作为学习完本题后的下一步挑战网格遍历类题目还可对照仓库中的 number-of-islands.md岛屿数量等文章体会标记访问这一通用模式。小结Word Search 是回溯算法在二维网格上的经典应用以每个单元格为起点、以四方向递归为路径、以标记 撤销管理状态。三种解法的差异集中在状态记录方式上——Hash Set 直观、Visited 数组常规、原地标记最省空间而仓库源码进一步展示了首字符剪枝、字符频次预检、单词反转、位运算编码等优化手段。掌握本题的递归骨架与状态管理思想即可平滑迁移到岛屿类问题、迷宫问题及 Word Search II 等进阶场景。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考