LeetCode-Book 题解精讲：79. 单词搜索——DFS 回溯与剪枝的经典范式

LeetCode-Book 题解精讲79. 单词搜索——DFS 回溯与剪枝的经典范式【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book导读本文基于《Krahets 笔面试精选 88 题》题单中的「79. 单词搜索」题解见 selected_coding_interview/docs/79. 单词搜索.md展开系统讲解如何在一个m × n的二维字符矩阵中判断给定单词能否由相邻单元格按顺序连接而成。读完本文你将掌握深度优先搜索DFS 回溯 剪枝的完整实现范式包括递归三要素参数、终止条件、递推工作、原地标记防重技巧空字符/\0以及O(3^K·MN)时间复杂度的推导过程同时结合本仓库 Python、Java、C 三份可直接运行的真实源码与测试用例验证实现细节。问题背景从题单到仓库「79. 单词搜索」是 README.md 中提及的《Krahets 笔面试精选 88 题》对应力扣题单 selected-coding-interview中的高频笔面试题本质上是二维网格上的路径搜索问题给定一个由字符组成的矩阵board和一个字符串word判断word是否存在于网格中。构成路径的相邻单元格要求水平或垂直相邻且同一个单元格内的字母不允许被重复使用。题目考察的核心能力有三点暴力枚举的建模能力把找单词转化为在所有可能的路径中寻找一条匹配串回溯Backtracking的落地能力在递归搜索失败后恢复现场继续探索其他分支剪枝的优化意识提前终止不可能匹配的分支避免指数级盲目搜索。本题在仓库中位于 selected_coding_interview 目录下与「剑指 Offer 12. 矩阵中的路径」是同一道题的变体因此掌握了本文的范式即可同时覆盖两本题单中的同源题目对应仓库 sword_for_offer 下的矩阵路径类问题。核心解题思路DFS 回溯 剪枝本题是典型的回溯问题官方题解给出的解决框架是深度优先搜索 剪枝二者的职责分工如下深度优先搜索DFS以暴力法遍历矩阵中所有字符串可能性。DFS 通过递归先朝一个方向搜到底再回溯至上一个节点沿另一个方向搜索以此类推直到穷尽所有可行路径。剪枝Pruning在搜索过程中一旦遇到这条路不可能和目标字符串匹配成功的情形——例如当前矩阵元素与目标字符不匹配、或该元素已被访问过——就立即返回从而砍掉整棵不可能成功的递归分支。可以这样理解整体流程从矩阵的每一个单元格出发把它当作word[0]尝试匹配匹配成功则向该单元格的上下左右四个邻居递归尝试匹配word[1]依此类推。整个过程相当于在一棵位置状态树上做深度优先遍历而剪枝负责在进入每个节点前判断这条路还有没有可能把明显无效的子树直接跳过。算法解析递归三要素回溯问题的实现核心是设计递归函数本题题解把递归函数dfs(i, j, k)的三个要素拆解得十分清晰1. 递归参数参数含义i, j当前元素在矩阵board中的行列索引k当前待匹配的目标字符在word中的索引递归进入第k层时目标是判断board[i][j]能否作为word[k]的匹配位置。2. 终止条件递归的终止分为失败返回与成功返回两类返回false的三种情况可用一条or语句合并行或列索引越界当前矩阵元素与目标字符word[k]不同当前矩阵元素已被访问过即被标记该情况可合并至第二条判定中一并处理。返回true的情况k len(word) - 1说明目标字符串word已全部匹配完毕找到了一条完整路径。注意第三条终止条件元素已访问过之所以能被合并进第二条正是因为访问标记使用了下文所述的空字符技巧——已被访问的元素其值不再是合法字符必然与word[k]不相等。3. 递推工作当board[i][j]成功匹配word[k]且尚未到达字符串末尾时进入递推阶段共三步标记当前元素将board[i][j]修改为空字符Python 为Java/C 为\0代表该元素已被访问防止后续搜索沿其他路径重复经过它搜索下一单元格朝当前元素的上、下、左、右四个方向开启下层递归各方向结果用或or/||连接——这意味着只要找到一条可行路径就直接返回true不再继续做无谓的 DFS还原当前元素将board[i][j]还原为初始值word[k]即回溯操作撤销标记使该单元格在后续其他起点的搜索中恢复可用。4. 返回值递归函数返回布尔量res代表从当前节点出发是否能够搜索到目标字符串的剩余部分最外层通过遍历矩阵所有起点只要有一个起点返回true则整个函数返回true否则返回false。为什么用空字符做访问标记使用空字符Python:Java/C:\0是为了防止标记字符与矩阵原有字符重复。如果用一个普通字符例如#做标记当矩阵本身含有该字符时算法会把矩阵原有的字符误判为标记从而出现错误匹配或漏匹配。三语言实现完整可运行的题解代码以下代码完整继承自题解文档与仓库中 codes/python/lc_79_word_search.py、codes/java/lc_79_word_search/lc_79_word_search.java、codes/cpp/lc_79_word_search/lc_79_word_search_s1.cpp 三份源码中的Solution主体完全一致。Python 实现class Solution: def exist(self, board: List[List[str]], word: str) - bool: def dfs(i, j, k): if not 0 i len(board) or not 0 j len(board[0]) or board[i][j] ! word[k]: return False if k len(word) - 1: return True board[i][j] res dfs(i 1, j, k 1) or dfs(i - 1, j, k 1) or dfs(i, j 1, k 1) or dfs(i, j - 1, k 1) board[i][j] word[k] return res for i in range(len(board)): for j in range(len(board[0])): if dfs(i, j, 0): return True return FalsePython 实现中not 0 i len(board)借助链式比较优雅地完成了越界判断board[i][j] 与board[i][j] word[k]分别对应标记与还原四个方向的递归用or短路连接任一方向成功即整体成功。Java 实现class Solution { public boolean exist(char[][] board, String word) { char[] words word.toCharArray(); for(int i 0; i board.length; i) { for(int j 0; j board[0].length; j) { if (dfs(board, words, i, j, 0)) return true; } } return false; } boolean dfs(char[][] board, char[] word, int i, int j, int k) { if (i board.length || i 0 || j board[0].length || j 0 || board[i][j] ! word[k]) return false; if (k word.length - 1) return true; board[i][j] \0; boolean res dfs(board, word, i 1, j, k 1) || dfs(board, word, i - 1, j, k 1) || dfs(board, word, i, j 1, k 1) || dfs(board, word, i , j - 1, k 1); board[i][j] word[k]; return res; } }Java 实现先调用word.toCharArray()把字符串转为字符数组避免递归中反复调用charAt的开销标记字符为\0。C 实现class Solution { public: bool exist(vectorvectorchar board, string word) { rows board.size(); cols board[0].size(); for(int i 0; i rows; i) { for(int j 0; j cols; j) { if (dfs(board, word, i, j, 0)) return true; } } return false; } private: int rows, cols; bool dfs(vectorvectorchar board, string word, int i, int j, int k) { if (i rows || i 0 || j cols || j 0 || board[i][j] ! word[k]) return false; if (k word.size() - 1) return true; board[i][j] \0; bool res dfs(board, word, i 1, j, k 1) || dfs(board, word, i - 1, j, k 1) || dfs(board, word, i, j 1, k 1) || dfs(board, word, i , j - 1, k 1); board[i][j] word[k]; return res; } };C 版本将rows、cols提升为类成员变量private区使递归函数无需反复调用board.size()标记字符同样使用\0。仓库源码与测试用例佐证本仓库为这道题提供了 Python、Java、C 三种语言的可执行源码每个文件都内嵌了相同的测试用例可直接编译运行验证语言源码路径测试用例Pythoncodes/python/lc_79_word_search.pyboard [[A,B,C,E],[S,F,C,S],[A,D,E,E]]word ABCCED期望输出TrueJavacodes/java/lc_79_word_search/lc_79_word_search.java同上经main中的 Driver Code 调用Solution.exist(...)并打印结果Ccodes/cpp/lc_79_word_search/lc_79_word_search_s1.cpp同上经main中new Solution()调用并cout输出以测试用例board [[A,B,C,E],[S,F,C,S],[A,D,E,E]]、word ABCCED为例可以手动推演一遍匹配路径从board[0][0] A出发按A → B → C → C → E → D的顺序依次向右、向下、向左、向右、向下移动最终整条路径连通返回True。三个文件的结构保持仓库统一的编排约定先是Solution解题代码段随后是Test Case测试输入与期望输出最后是Driver Code实例化Solution并打印结果。Python 文件顶部from include import *引入 include 公共模块Java/C 分别通过import include.*与#include ../include/include.hpp引入各自语言的公共头文件/工具类。若想自行验证其他用例只需修改源码中Test Case部分的board与word后重新运行即可例如将word改为ABCB并运行预期输出为False因为B会被A路径重复占用违反同一单元格不可重复使用的约束。复杂度分析设矩阵大小为M × N目标字符串word长度为K题解给出的复杂度结论如下时间复杂度O(3^K · MN)最差情况下需要遍历矩阵中长度为K的字符串的所有可行方案。方案数计算设字符串长度为K搜索中每个字符有上、下、左、右四个方向可以选择但需要舍弃回头即上个字符所在的方向因此每个节点实际剩下3 种选择方案数的复杂度为O(3^K)起点数量矩阵中共有MN个起点每个单元格都可能作为word[0]故整体为O(3^K · MN)。需要说明的是这是最坏情况的渐进上界实际运行时由于剪枝字符不匹配立即返回的存在大多数分支在很浅的层级就会被终止运行时间通常远小于理论最坏值。空间复杂度O(K)搜索过程中的递归深度不超过K因此系统因函数调用累计使用的栈空间占用为O(K)函数返回后系统调用的栈空间会被释放。最坏情况下K MN即单词路径贯穿整个矩阵递归深度为MN此时系统栈使用O(MN)的额外空间。除递归栈外算法没有申请与矩阵规模相关的额外辅助空间访问标记直接原地写入board不另开visited数组。范式小结从一道题到一类题「单词搜索」是回溯算法的教科书级例题其递归三要素 原地标记 四方向或连接的写法可以迁移到大量网格搜索类问题上棋盘/网格路径搜索类如「剑指 Offer 12. 矩阵中的路径」与本题同源、「200. 岛屿数量」等均可沿用四方向 DFS 防重标记的骨架回溯组合类本仓库 46. 全排列、47. 全排列 II 等题目同样依赖递归进入 失败还原现场的回溯思想区别仅在于状态空间是排列而非网格路径优化方向当矩阵规模较大或单词较长时可进一步引入**单词前缀树Trie**预处理在一次 DFS 中同时匹配多个单词对应 LeetCode 212. 单词搜索 II这是本题的自然延伸考点。掌握本题的 DFS 剪枝范式后遇到同类在状态空间中寻找一条满足约束的路径的问题都可以快速套用这套思考框架。更多同类题解与配套源码可在仓库 selected_coding_interview 的 docs 与 codes 目录中按题目编号查阅。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考