很多刷LeetCode的人走到“热题100”的中间阶段都会撞上这道单词搜索思路一看就懂代码一写就错调试两小时是常有的事。它属于典型的二维网格上的回溯问题不只是考察递归基本功还顺带考察你对“状态还原”“剪枝时机”“复杂度估算”的理解。我最早在准备面试时反复做了三遍每次都有新感受这篇文章就把这道题的完整拆解、代码写法、踩坑记录全部放出来适合刚开始刷回溯、准备技术面试、或者想彻底搞懂 DFS 在网格上怎么用的朋友。1. 题目理解与解题思路拆解1.1 题目到底在考什么原题是 LeetCode 79题面很简洁给你一个m x n的字符网格board和一个字符串word判断这个单词是否存在于网格中。所谓“存在”是指按照单词的字母顺序从一个格子上、下、左、右四个方向依次移动能拼出这个单词而且同一个格子不能被重复使用。看上去像一个“找路径”问题但它和单纯的图搜索不一样路径的长度定死了必须等于word的长度路径的每一步都要和word对应位置字符相等。所以它本质上是在网格里做精确匹配拼的不是最短路径而是要一步一步验证是否存在这样一条连续的、无重复格子的匹配路线。这道题放在热题 100 里典型目的是考察三件事。第一递归回溯的代码组织能力第二在二维数组上做访问控制哪些格子走过了第三时间复杂度的粗略估算能力。面试官往往不会只满足于你说“用 DFS”他会继续追问“为什么能用 DFS怎么剪枝最坏情况时间复杂度多少能不能优化”如果只是背个模板很容易被问穿。1.2 为什么第一反应是回溯而不是其他算法第一次看到这道题有人会想到图论 BFS、动态规划、甚至字典树但真正的第一选择就是回溯也就是带状态恢复的深度优先搜索。原因很直接路径长度不定但有限word长度可能很短也可能接近网格大小不需要预先计算所有路径。需要记录访问历史必须知道当前递归深度下哪些格子已经用过了。BFS 也可以做但要维护路径集合编码复杂度高。需要剪枝走错了要回退重新选择方向这就是回溯的“撤销动作”。用一个生活化的类比你在迷宫里找一个特定的字母序列每走一步必须踩到正确的字母。走错了就退回到上一个交叉口换一个方向继续试。退回来的时候还要把刚才踩过的格子“擦掉”标记否则下一次从其他路径走时会误以为这个格子已经被占了。这个“擦掉标记”的操作就是回溯中最关键的状态恢复。2. 核心细节回溯实现的关键环节2.1 方向数组与边界检查网格上从一个格子往相邻格子走规则固定上、下、左、右。很多人用四个方向的if语句分别判断代码又长又容易漏。标准做法是准备一个方向数组int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1};新的行坐标是nx x dx[i]新的列坐标是ny y dy[i]。为什么用方向数组而不是写四个递归调用因为逻辑统一后面如果要改成八方向对角线也算相邻只需要把数组扩成8个元素递归体完全不用动。可维护性高也不容易在复制粘贴时漏改边界。边界检查必须放在访问递归入口处先判断越界再判断字符是否匹配。顺序不能反。很多人栽在board[nx][ny]时数组越界就是因为没先做nx 0 nx m ny 0 ny n的判断。提示这类棋盘题的边界条件最好集中写成一个isValid函数或者写在递归开头用一条if短路掉。别在调用方反复判断否则嵌套一多脑子就乱了。2.2 状态标记与恢复的时机同一个格子不能重复使用这意味着递归时必须记录每个格子是否被当前路径占用。最简单直观的做法是开一个二维visited数组访问时置true递归返回后置回false。但还有一个更轻量的技巧直接复用board本身把当前格子字符临时修改成一个不会出现在单词里的特殊字符比如#递归返回后再恢复成原字符。这样做省掉了额外m * n的内存代码也更紧凑。# 以Python伪代码展示核心逻辑 def backtrack(board, word, i, j, k): if k len(word): return True if i 0 or j 0 or i len(board) or j len(board[0]): return False if board[i][j] ! word[k]: return False # 临时占用当前格子 temp board[i][j] board[i][j] # # 四个方向递归 res (backtrack(board, word, i1, j, k1) or backtrack(board, word, i-1, j, k1) or backtrack(board, word, i, j1, k1) or backtrack(board, word, i, j-1, k1)) # 恢复格子 board[i][j] temp return res状态恢复的时机很讲究res的计算必须包含四个方向的递归调用等全部结束之后再恢复当前格子。如果恢复动作写在某个if分支里或者提前return就会破坏状态的一致性。还有一种常见错误是在递归返回后忘了恢复导致后续搜索把已访问格子误判为不可用结果漏掉正确路径。2.3 剪枝技巧从入口到逐字符匹配剪枝的核心是“提前终止不可能的分支”。这道题最简单的剪枝有两个入口剪枝遍历所有格子作为起点时如果board[i][j] ! word[0]直接跳过根本不需要进入递归。长度剪枝如果word的长度大于所有单元格数量直接返回False。递归过程中的剪枝一旦在某一步发现字符不匹配立刻返回False不再往下深挖。这三个剪枝看似简单实际效果非常明显。尤其是在网格较大、单词较短的情况下入口剪枝能砍掉大量无效递归。如果单词开头字母在网格中出现频率很低性能提升一个量级都不夸张。另一个容易忽略的剪枝是“计数剪枝”先统计word中每个字母的出现次数再统计网格中这些字母的总数。如果word中某个字母在网格里的数量少于它需要的数量直接返回False。这个剪枝实现起来就是两个哈希表或数组的对比代价低对极端用例很有效。3. 完整代码实现与逐段解读3.1 使用 C 实现主流程C 实现时要注意递归函数的参数传递。网格和单词建议用引用传递避免每次递归都复制一份容器。参考实现如下class Solution { public: int m, n; bool exist(vectorvectorchar board, string word) { m board.size(); n board[0].size(); // 长度剪枝 if (word.size() m * n) return false; for (int i 0; i m; i) { for (int j 0; j n; j) { if (board[i][j] word[0]) { if (dfs(board, word, i, j, 0)) { return true; } } } } return false; } bool dfs(vectorvectorchar board, string word, int i, int j, int idx) { if (idx word.size()) return true; if (i 0 || j 0 || i m || j n) return false; if (board[i][j] ! word[idx]) return false; char temp board[i][j]; board[i][j] #; bool found dfs(board, word, i 1, j, idx 1) || dfs(board, word, i - 1, j, idx 1) || dfs(board, word, i, j 1, idx 1) || dfs(board, word, i, j - 1, idx 1); board[i][j] temp; return found; } };这段代码有个细节found的赋值用的是||而不是分开的四个if。好处是短路求值一旦某个方向返回True后面的方向根本不会执行。注意这里有一个隐藏坑递归调用传的是idx 1不是idx。传idx会改变当前层idx的值导致后续方向判断错乱。temp保存当前格子的原始字符递归结束后再恢复。如果忘记恢复或者恢复时用了别的字符调试时会发现路径正确但结果错误非常隐蔽。3.2 使用 Python 实现主流程Python 写法更简洁但要注意递归深度。Python 默认递归深度约 1000如果word长度达到好几百可能会RecursionError。因此递归函数内部不要写无谓的嵌套层级。class Solution: def exist(self, board: List[List[str]], word: str) - bool: m, n len(board), len(board[0]) if len(word) m * n: return False def dfs(i: int, j: int, k: int) - bool: if k len(word): return True if i 0 or j 0 or i m or j n: return False if board[i][j] ! word[k]: return False temp, board[i][j] 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] temp return res for i in range(m): for j in range(n): if board[i][j] word[0] and dfs(i, j, 0): return True return FalsePython 的List类型需要从typing导入LeetCode 环境里已经默认带好不用自己额外处理。另一个值得注意的点Python 嵌套函数闭包引用word、board不需要声明nonlocal因为这里没有对它们重新赋值只是修改board[i][j]这种元素。如果你试图对word直接赋值就会因为闭包作用域报错但这里不会。3.3 两种实现的差异与选型建议从执行效率看C 在递归调用开销和容器访问上通常比 Python 快不少。但从面试实战看Python 代码更短出错概率更低。如果目标是快速在 LeetCode 上 ACPython 足够如果目标是面试手写代码且面试官要求 C那就用上面那段 C 逻辑。选型上还有一个考虑是否允许修改原数组LeetCode 解法普遍允许因为提交后每次调用都是独立用例不影响数据。但在真实面试中如果面试官强调“不要修改输入数据”你就得用visited数组。用visited时需要额外申请m * n的布尔空间并且在递归开始时标记、递归结束时取消标记。逻辑与修改board的方式完全对称但代码量会多一些。4. 复杂度分析与优化思考4.1 时间与空间复杂度是怎么来的时间复杂度最坏为O(m * n * 4^L)其中L是word的长度。推导过程不复杂网格有m * n个起点每个起点最多向四个方向扩展每扩展一层最多再乘 4所以是m * n * 4^L量级。但这个量级在具体用例中通常达不到因为字符匹配会剪掉大量分支。最坏情况需要构造一个极端例子比如网格里全是a单词也是一长串a此时每个格子都有四个方向可以走几乎无法剪枝复杂度会非常难看。空间复杂度方面如果使用board本身做标记额外空间为O(1)递归栈的深度最大为L所以总空间为O(L)。如果使用visited数组额外空间为O(m * n)总计仍是O(L m * n)但本质上多了一块常量级相对网格的开销。关于复杂度的表述面试时一定要说明“最坏情况”和“实际平均情况”的区别。”最坏“是理论分析”实际“受剪枝影响很大。这样既严谨又能体现你对算法性能的监控意识。4.2 经典优化Trie 树预处理的场景LeetCode 里还有一道进阶题212 单词搜索 II要求在同一个网格里查找多个单词。如果对每个单词单独跑一遍上面的回溯复杂度就会乘以单词数量很容易超时。常规优化是用Trie前缀树预处理所有目标单词然后从网格每个点出发一边走一边匹配前缀。匹配到某个节点时如果发现它是一个单词的结尾就收集答案如果当前前缀不再对应任何目标单词就立即停止深入。这就是 BFS/DFS 与 Trie 结合的典型场景。回到本题只有一个单词时不需要 Trie因为没有任何可复用的前缀信息引入 Trie 反而增加开销。很多人在理解优化时会过度设计面试时用力过猛。先把基础回溯写对再补充一句“如果单词非常多我会用 Trie 优化”这就够了。4.3 还能怎么变着考面试官不会满足于你背过这题。常见的变形有求所有匹配路径的坐标不只返回True/False而是要求输出路径。做法是在递归参数中带一个vectorpairint,int path找到后拷贝一份到结果集。注意此时不能用短路返回必须遍历完所有方向。网格中有障碍物某个格子不可通行路径不能踩上去。只需要在进入递归时判断该格子是否为障碍。改变方向的约束比如“不能连续走同一个方向”“最多拐弯两次”。这类约束只需要在递归参数中增加方向编号和拐弯次数两个变量本质上还是状态扩展。理解了回溯的底层逻辑变形题只是往递归参数里多塞几个状态字段的事。5. 实战踩坑与调试经验5.1 高频 Bug 清单回顾我和身边同事写这题踩过的坑主要集中在下面几个地方错误类型具体表现排查方法边界越界访问board[nx][ny]时数组下标超出范围在递归开头先判断所有边界条件再访问字符忘记状态恢复搜索完一个分支后#残留在网格中打印每一层递归前后board的变化肉眼对比提前返回找到一个方向匹配就return true没有遍历其它方向确认返回值是用 数组下标写反把行号写成列号导致在矩形网格上奇偶错位用 3x4 的小网格手动推导一次长度剪枝缺失word长度超过网格数量时仍然遍历在入口处加len(word) m * n判断短路求值副作用递归函数内部修改了外部状态导致后一个分支受影响保证状态恢复在递归调用之后统一执行其中“忘记状态恢复”是最隐蔽的。因为当第一个分支失败时第二个分支本可以经过刚才那个格子但格子被标记成了占用的#这条路就被堵死了。结果程序返回false可你明明觉得解法是对的。5.2 遇到超时怎么办很多人第一版通过了样例但提交时遇上比较大的网格和长单词直接 TLE。超时后优先检查三件事。第一是否在最外层循环里对所有格子都调用了递归哪怕board[i][j]和word[0]不相等如果没加入口剪枝会白白发起大量递归这通常是超时的首要原因。第二递归中是否做了无意义的重复工作例如有人在递归里重新申请一个visited二维数组传给下一层这就把原本 O(1) 的状态记录变成 O(m*n) 复制性能爆炸。第三是否可以通过短路的||避免多个方向同时递归如果代码写成先递归完四个方向再用if (a || b || c || d) return true;Python 的或表达式本身就会短路没有额外问题。但如果用列表存储四个方向的bool结果再一起判断就失去了短路带来的性能优势。一般来说做完这三步极端用例的耗时能明显下降。5.3 面试时的展示技巧面试时写这题建议按四步来展示先和面试官确认输入输出board是否可以修改word是否可能为空网格行列是否可能为 0这些确认过程体现了严谨性非常加分。画出搜索树用一个小用例比如 2 行 2 列网格匹配 “ABDC”在纸上画出递归的扩展与回退过程帮自己和面试官理清回溯路径。写代码时强调状态恢复在写完board[i][j] temp;那一行时主动解释“这行是核心保证每个分支结束后现场还原”。说复杂度先给出最坏情况O(m*n*4^L)再补充一句“如果加计数剪枝实践中会好很多”。我个人在实际面试中还会额外提一句“如果单词特别长可以考虑把网格和单词的字符统计对比剪枝或者考虑用双向搜索/哈希预处理减少方向扩展数”这会让面试官觉得你不只会背题而是有优化嗅觉。回到这道题本身它真正教会我的不是 DFS 怎么写而是“如何在有约束的搜索空间里用撤销动作来保证每一层决策的独立性”。你如果已经把上面的代码完完整整写了两遍并且能不看题解独立 AC那这道热题 100 基本就吃透了。后续再遇到矩阵、棋盘、岛屿类回溯题很多套路都会觉得似曾相识。