企业官网建设流程全解析

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. 递归参数

递归进入第k层时，目标是判断board[i][j]能否作为word[k]的匹配位置。

2. 终止条件

递归的终止分为"失败返回"与"成功返回"两类：

1. 返回false的三种情况（可用一条or语句合并）：
   • 行或列索引越界；
   • 当前矩阵元素与目标字符word[k]不同；
   • 当前矩阵元素已被访问过（即被标记，该情况可合并至第二条判定中一并处理）。
2. 返回true的情况：k == len(word) - 1，说明目标字符串word已全部匹配完毕，找到了一条完整路径。

注意第三条终止条件"元素已访问过"之所以能被合并进第二条，正是因为访问标记使用了下文所述的空字符技巧——已被访问的元素其值不再是合法字符，必然与word[k]不相等。

3. 递推工作

当board[i][j]成功匹配word[k]且尚未到达字符串末尾时，进入递推阶段，共三步：

1. 标记当前元素：将board[i][j]修改为空字符（Python 为''，Java/C++ 为'\0'），代表该元素已被访问，防止后续搜索沿其他路径重复经过它；
2. 搜索下一单元格：朝当前元素的上、下、左、右四个方向开启下层递归，各方向结果用或（or/||）连接——这意味着只要找到一条可行路径就直接返回true，不再继续做无谓的 DFS；
3. 还原当前元素：将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 False

Python 实现中，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(vector<vector<char>>& 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(vector<vector<char>>& 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++ 三种语言的可执行源码，每个文件都内嵌了相同的测试用例，可直接编译运行验证：

以测试用例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数组）。

范式小结：从一道题到一类题

「单词搜索」是回溯算法的教科书级例题，其"递归三要素 + 原地标记 + 四方向或连接"的写法可以迁移到大量网格搜索类问题上：

1. 棋盘/网格路径搜索类：如「剑指 Offer 12. 矩阵中的路径」（与本题同源）、「200. 岛屿数量」等，均可沿用"四方向 DFS + 防重标记"的骨架；
2. 回溯组合类：本仓库 46. 全排列、47. 全排列 II 等题目同样依赖"递归进入 + 失败还原现场"的回溯思想，区别仅在于状态空间是排列而非网格路径；
3. 优化方向：当矩阵规模较大或单词较长时，可进一步引入**单词前缀树（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