LeetCode Hot100 刷到第79题“单词搜索”的朋友多半都有类似的经历看题解觉得“就这”三分钟看懂关上题解自己一写越界、死循环、字符没恢复的问题全冒出来了。这道题是二维网格上做回溯搜索的经典代表也是DFS从“树的遍历”升级到“图上路径搜索”的第一道坎。这篇文章不打算只给你贴一份能AC的代码而是把这个题彻底拆开题目在考什么、回溯为什么这么设计、代码里每一行在干什么、哪些剪枝真正有用最后再把它和同类题串起来。不管你是刚开始刷Hot100还是面试前想快速复习这篇都能帮你把这道题吃透以后遇到 79. 单词搜索 的变形题也不至于慌了手脚。1. 这道题到底在考什么——题目还原与考点拆解1.1 先把题目翻译成人话题目给一个 m 行 n 列的字符矩阵 board一个字符串 word。你要判断能不能在 board 里“走”出一条路径路径上的字符按顺序拼起来刚好等于 word。走法很简单从任意一个格子出发每次只能走到上下左右相邻的格子而且同一个格子只能用一次。举个例子board 长这样A B C E S F C S A D E Eword ABCCED 是可以找到的路径是 (0,0)-A → (0,1)-B → (0,2)-C → (1,2)-C → (2,2)-E → (2,1)-D。但 word ABCB 就找不到因为 C 用过一次之后不能回头再用。注意“一个格子只能用一次”这句话是整道题最容易翻车的地方。很多人的第一版代码死循环就是因为没处理这个限制。比如路径走完 (0,2) 的 C下一步又走回 (0,1) 的 B如果 B 已经被访问过就不会陷入无限递归。这里体现的是状态管理的基本功。1.2 考点拆解三层递进的能力考察第一层能不能想到用 DFS。看到“从当前格子向四周扩展”就应该条件反射地去想深度优先搜索。每个格子就是搜索树的一个节点上下左右四个方向就是四条分支。第二层能不能正确实现“回溯”。搜索过程中一条路走到底发现不行要退回上一个分岔口重新选路。这个“回到上一个分岔口”不是简单的函数返回而是要把之前做的状态修改全部撤销。很多人栽在这里——只做了标记没做恢复结果路径之间互相干扰。第三层能不能正确管理“已访问”状态。visited 数组或者原地标记是 DFS 在图上搜索和树上搜索最核心的区别。树没有环路不需要标记图上有环路不标记就会无限递归。这道题的本质就是在二维网格图上做路径搜索标记必不可少。这三层能力是逐级嵌套的想到 DFS 是入门正确回溯是关键状态管理则是区分“背过模板”和“真正理解”的分水岭。1.3 为什么它是 Hot100 的常客这道题在面试里出现频率很高我觉得有三个原因。第一题目简短不涉及复杂的数据结构非常适合作为手写题在 45 分钟内考察。面试官可以从最简单的暴力枚举开始引导一步步看候选人能不能想到回溯属于“难度可控、区分度很高”的题。第二它特别容易暴露基本功。边界判断有没有先做、字符恢复的位置对不对、起始点遍历有没有漏两三分钟就能看出一个人的代码习惯和熟练度。第三它是一类题的地基。LeetCode 上不少题目是它的变形212 题单词搜索 II 要处理多个单词329 题矩阵中的最长递增路径本质是带记忆化的 DFS连 51 题 N 皇后、39 题组合总和这类经典回溯题核心的“状态管理”思路和它一模一样。2. 思路推演——从暴力枚举到回溯的完整链路2.1 为什么不能把所有路径都枚举出来最直接的想法枚举出 board 中所有可能的路径看能不能拼出 word。稍微算一下就知道不现实。每个格子出发最多有 4 个方向路径每延伸一步可能性乘 4路径长度为 L 时总路径数是 m * n * 4^L 数量级。假设 board 是 6x6word 长度是 154^15 大概是 10 亿量级这个规模根本枚举不完。而且这里面有大量的浪费很多路径在第二个字符就已经和 word[1] 不匹配了根本不用继续往下走。真正聪明的做法是边走边验证一旦发现当前字符不匹配立刻放弃这条分支。关键洞察是我们不是在找“所有路径”而是在找“一条能匹配 word 的路径”。搜索过程中只要发现当前路径已经不可能匹配了就应该立即放弃而不是等走到头才发现白走了。这个“发现不可能就立刻止损”的动作就是剪枝。2.2 递归天然适配“一条路走到黑”DFS 的核心是栈式扩展从起点出发选一个方向一直走下去不行再退回来选别的方向。这个“走到底再回头”的过程和递归的调用栈配合得非常完美——每次进入新的函数调用就是往深处走一层函数返回时就是退回到上层。所以用递归实现 DFS 是水到渠成的事。dfs(i, j, k)这个函数的语义可以定义为当前在board[i][j]已经匹配了 word 的前 k 个字符接下来要向四周寻找能匹配word[k]的格子。k 从 0 走到len(word)就算成功。这里有个容易混淆的细节有人用 k 表示“已经匹配了几个字符”有人用 k 表示“当前要匹配第几个字符”。两种写法都能 AC但建议初学者用前者写终止条件k len(word)更直观不容易搞混。如果你在写代码时经常被索引问题绕晕不妨直接在纸上画一个长度为 3 的单词把 k0、k1、k2、k3 的递归状态写出来理清每一步匹配的是哪个字符边界问题会清晰很多。2.3 回溯的三步曲尝试、递归、回退回溯可以总结成三个动作。尝试把当前格子标记为“已访问”表示它进入了当前路径。递归从当前格子向四个方向继续扩展。回退四个方向都试完还没找到答案说明以当前格子开头的这条路走不通。此时撤销当前格子的“已访问”标记让后续其他路径能重新使用这个格子。拿走迷宫类比你在每个路口撒一把沙子做标记防止走重复路。但回溯的迷宫更特殊——当你从一条死胡同退回分岔口换另一条路走时如果这条新路也要经过之前某个路口那把沙子的标记擦掉。这里的标记是临时性质的撤销动作是回溯的灵魂。为什么必须撤销假设从 (0,0) 出发探索了一条经过 (1,1) 的路失败了。退回后换一条新路这条新路可能也要经过 (1,1)。如果 (1,1) 的标记没擦掉新路就被堵死了搜索会漏掉正确答案。所以每一层递归返回时都要把自己加的标记恢复原样。3. 代码实现与逐行解读——两个版本的核心差异3.1 标准写法visited 数组版本class Solution: def exist(self, board: List[List[str]], word: str) - bool: m, n len(board), len(board[0]) visited [[False] * n for _ in range(m)] directions [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(i: int, j: int, k: int) - bool: # 1. 终止条件所有字符都匹配完 if k len(word): return True # 2. 越界检查 if i 0 or i m or j 0 or j n: return False # 3. 已访问过或字符不匹配剪掉 if visited[i][j] or board[i][j] ! word[k]: return False # 4. 标记当前格子已访问 visited[i][j] True # 5. 向四个方向扩展 for di, dj in directions: if dfs(i di, j dj, k 1): return True # 6. 四个方向都失败撤销标记 visited[i][j] False return False # 枚举所有起始格子 for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False这段代码的核心逻辑就 8 行左右。逐段解释一下。第 2 行的k len(word)是终止条件。注意它必须放在越界检查之前。为什么不先检查越界因为当 k 已经等于 len(word) 时i 和 j 可能是上一轮递归向越界方向多走一步产生的新坐标。如果先检查越界函数会直接返回 False但此时 word 已经全部匹配完正确答案应该是 True。所以终止条件要放在最前面。第 3 行的越界检查很关键。每次向上下左右扩展一格后新坐标可能超出 board 边界必须在访问board[i][j]之前先判断。Python 的列表索引如果是负数比如board[-1][0]不会报错而是访问最后一行这会造成非常隐蔽的 bug——看起来没越界实际上已经跑到了错误的格子上。第 4 行的visited[i][j] or board[i][j] ! word[k]把“已经走过的格子”和“字符不匹配”合并剪掉。这里的短路逻辑很有用先判断是否访问过省一次字符比较字符不匹配时也直接剪掉不用进入下一步递归。第 6 行把visited[i][j]恢复为 False。这句是回溯的核心。漏掉它后面其他起点或者其他路径需要使用这个格子时就被挡住了出现漏解。你可以自己做一个实验把第 6 行注释掉用board [[A,B],[C,D]]、word ABDC跑一下大概率会得到错误结果。3.2 空间优化版原地修改 board既然已经知道当前格子是board[i][j]而且会在返回前恢复可以直接把board[i][j]改成任意一个在 board 中不可能出现的字符作为临时标记。这样省掉了 m * n 的 visited 数组空间。class Solution: def exist(self, board: List[List[str]], word: str) - bool: m, n len(board), len(board[0]) def dfs(i: int, j: int, k: int) - bool: if k len(word): return True if i 0 or i m or j 0 or j n: return False if board[i][j] ! word[k]: return False tmp board[i][j] board[i][j] # # 原地标记 for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]: if dfs(i di, j dj, k 1): return True board[i][j] tmp # 恢复原字符 return False for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False这个版本的核心假设是 board 里的字符不包含#。LeetCode 上 board 输入只包含大小写英文字母所以用#是安全的。如果你自己造测试数据时 board 里可能有#就换成\0或者干脆用 visited 数组。这个细节隐藏在“为什么要选这个标记字符”里面试时主动提一句会加分。两个版本的时间复杂度一样都是 O(m * n * 4^L)L 是 word 长度。空间上 visited 数组版本是 O(m * n)原地标记版本递归深度为 L调用栈空间是 O(L)不计算额外数组的话是 O(1)。3.3 最容易写错的三个细节第一个终止条件和越界检查的顺序。前面已经强调过k len(word)必须在最前面。如果先检查越界word 匹配完但坐标恰好越界时会返回 False正确答案应该是 True。这个错误非常经典毕竟递归是“先进入下一层再判断条件”很多人在写递归的时候会不自觉地调整条件的顺序导致边界问题。第二个visited 的恢复要放在循环外面还是里面。答案是放在循环外面、return False之前。有人会把撤销写在 for 循环的每个分支里导致代码重复且容易漏。统一在四个方向都尝试完之后执行一次最干净也最保险。第三个起始点枚举的时机。注意主函数里对每个格子都调用了dfs(i, j, 0)。有一种错误写法是只从 (0,0) 开始 dfs找不到就换个起点但 visited 数组没有清空。正常回溯的话每个起点搜完 visited 应该全部恢复为 False。如果你发现某个起点搜完后 visited 不是全 False说明回溯代码写错了而不是要去手动清空数组。这个点理解之后你的代码就稳了一大半。4. 剪枝实测——哪些优化真能提速哪些只是自我感动4.1 字符频率预判O(m*n) 完成最强剪枝LeetCode 的单词搜索因为 board 和 word 都比较小不加剪枝也能过。但面试时能主动提剪枝会是不错的加分项。最实用的第一个剪枝是字符频率预判统计 word 中每个字符的数量如果某个字符在 word 中出现的次数大于在 board 中出现的次数直接返回 False。from collections import Counter word_counter Counter(word) board_counter Counter(.join(.join(row) for row in board)) if word_counter - board_counter: return False这里的word_counter - board_counter会得到“word 中比 board 多的那些字符”如果结果非空说明 board 里根本没有足够的字符去拼出 word直接返回 False。这个剪枝在极端情况下效果非常明显。比如 word 是AAAAA而 board 里只有两个 A那无论怎么搜索都不可能拼出来。一次 O(m*n) 的预判能省掉后续所有搜索。成本极低逻辑完全正确不会误伤答案。4.2 方向选择从分支少的端点开始搜还有一个进阶思路如果word[0]在 board 中出现的次数远多于word[-1]可以选择从最后一个字符开始反向搜索。原理不复杂word[0]出现越多可选的起点就越多搜索树的分支就越多反过来从出现次数少的末尾字符开始搜起点的数量急剧减少搜索空间就小了。这是回溯题通用的优化思路——优先从分支最少的端点开始搜索。我实测过一个极端 caseword 是AAAAAAABboard 里有大量 A 但只有一个 B 作为结尾。正向搜索需要枚举大量起点每次都沿着 A 的路径往下探反向搜索则在找到唯一的 B 之后只需要沿着 A 的路径反着走一遍速度提升非常明显。具体实现上可以在主函数里判断一下 word 首尾字符在 board 中的出现次数如果board_counter[word[0]] board_counter[word[-1]]就把 word 反转再搜索。注意反转后匹配逻辑不用改因为路径是可逆的——正向能拼出来反向也能拼出来。4.3 剪枝不是越多越好别破坏正确性剪枝要注意一件事必须保证逻辑绝对正确不能为了提速牺牲正确性。比如网上有人提过“当前格子剩余可走的步数不足以匹配 word 剩余部分时剪枝”但这个论断需要额外保证“每个格子只能走一次”的前提下剩余可走的格子数计算要非常小心否则很容易误剪。稳妥的做法只用字符频率预判这类逻辑上绝对正确的剪枝就够了。还有一点想提醒LeetCode 的评测 case 比较温和这些优化不一定在绝对时间上拉开多大差距。但面试时主动提“我先做了字符频率预判再根据首尾字符频率决定是否反向搜索”面试官会看到你对复杂度的理解和对边界场景的敏感度。这才是剪枝真正的价值所在——它不是给你省那几毫秒的而是展示你思维深度的。4.4 不同写法对比实现方式改动成本核心收益风险点无剪枝 visited 版本基础写法逻辑清晰适合学习无字符频率预判加 3-4 行极端 case 直接返回 False几乎无风险反向搜索中需判断首尾频率起点少时提速明显需注意反转逻辑原地标记 board低省 O(m*n) 空间标记字符可能与 board 冲突5. 举一反三——从单词搜索到一整类回溯题5.1 单词搜索 II多加一棵 Trie 树LeetCode 212 题单词搜索 II给的是一组 words要求返回所有能在 board 中找到的单词。如果对每个单词单独跑一遍单词搜索的 DFSwords 很多时效率非常低。经典解法是把所有 words 插入一棵 Trie字典树然后在 board 上做 DFS。每到一步都判断当前路径字符组成的字符串是不是某个单词的前缀。如果是继续扩展如果不是剪枝如果到达某个单词的结尾就记录下来。Trie 在这里充当的就是“公共前缀剪枝器”。回溯的思想没变区别只是匹配目标从单个 word 变成了共享前缀。掌握单词搜索之后再看单词搜索 II难点其实只剩 Trie 的构建和遍历回溯部分反而是熟悉的套路。5.2 和岛屿类题目的一字之差LeetCode 上还有大量岛屿类题目比如 200 题岛屿数量、130 题被围绕的区域。它们也用 DFS但有一个关键区别岛屿类题目不需要回溯只需要遍历。因为岛屿题的目标是“把整块连通的区域标记出来”一旦一个格子被标记为已访问就再也不会被撤销而单词搜索的目标是“找一条匹配的路径”一个格子当前路径失败后可能在另一条路径里会被再次用到。这个区别可以总结成一句话需要找一条路径的用回溯需要找所有连通块的用普通 DFS 或 BFS。判断标准就是看“这个格子被访问标记后以后还有没有必要再被访问”。如果没必要说明是一锤子买卖的连通性问题如果有必要说明是路径探索问题需要完整的回溯机制。5.3 一套能迁移的通用回溯模板把单词搜索的精髓抽成模板可以适配很多路径搜索类回溯题def backtrack(状态, 匹配深度k): if k 目标长度: return True for 每个相邻状态: if 状态不合法: continue 做状态修改 if backtrack(新状态, k 1): return True 撤销状态修改 return FalseN 皇后问题里用 col 数组标记哪些列被占用这就是“做状态修改/撤销修改”的具体化组合总和问题里用 startIndex 控制可选集合的范围本质上也是回溯。状态管理的方式不同但骨架完全一致。个人经验是刷题不用贪多。把单词搜索这一道题吃透到“能闭眼写出、能给面试官讲清楚每一步为什么”的程度比囫囵吞枣做十道更有效。面试时如果遇到回溯题思路会非常顺畅因为底层的“状态管理”这一关你已经彻底过了。最后分享一个我刷这道题的体会第一次 AC 之后别急着做下一题。试着把 visited 数组改成原地标记再写一遍改完再试着手写一个非递归的栈版本不用系统递归。这几步折腾下来你对“递归调用栈”和“回溯状态恢复”的理解会上一个台阶。LeetCode Hot100 里回溯章节的题不少但绝大多数核心思想都能在 79 题里找到源头。
LeetCode 79. 单词搜索：回溯算法与DFS状态管理全解析
LeetCode Hot100 刷到第79题“单词搜索”的朋友多半都有类似的经历看题解觉得“就这”三分钟看懂关上题解自己一写越界、死循环、字符没恢复的问题全冒出来了。这道题是二维网格上做回溯搜索的经典代表也是DFS从“树的遍历”升级到“图上路径搜索”的第一道坎。这篇文章不打算只给你贴一份能AC的代码而是把这个题彻底拆开题目在考什么、回溯为什么这么设计、代码里每一行在干什么、哪些剪枝真正有用最后再把它和同类题串起来。不管你是刚开始刷Hot100还是面试前想快速复习这篇都能帮你把这道题吃透以后遇到 79. 单词搜索 的变形题也不至于慌了手脚。1. 这道题到底在考什么——题目还原与考点拆解1.1 先把题目翻译成人话题目给一个 m 行 n 列的字符矩阵 board一个字符串 word。你要判断能不能在 board 里“走”出一条路径路径上的字符按顺序拼起来刚好等于 word。走法很简单从任意一个格子出发每次只能走到上下左右相邻的格子而且同一个格子只能用一次。举个例子board 长这样A B C E S F C S A D E Eword ABCCED 是可以找到的路径是 (0,0)-A → (0,1)-B → (0,2)-C → (1,2)-C → (2,2)-E → (2,1)-D。但 word ABCB 就找不到因为 C 用过一次之后不能回头再用。注意“一个格子只能用一次”这句话是整道题最容易翻车的地方。很多人的第一版代码死循环就是因为没处理这个限制。比如路径走完 (0,2) 的 C下一步又走回 (0,1) 的 B如果 B 已经被访问过就不会陷入无限递归。这里体现的是状态管理的基本功。1.2 考点拆解三层递进的能力考察第一层能不能想到用 DFS。看到“从当前格子向四周扩展”就应该条件反射地去想深度优先搜索。每个格子就是搜索树的一个节点上下左右四个方向就是四条分支。第二层能不能正确实现“回溯”。搜索过程中一条路走到底发现不行要退回上一个分岔口重新选路。这个“回到上一个分岔口”不是简单的函数返回而是要把之前做的状态修改全部撤销。很多人栽在这里——只做了标记没做恢复结果路径之间互相干扰。第三层能不能正确管理“已访问”状态。visited 数组或者原地标记是 DFS 在图上搜索和树上搜索最核心的区别。树没有环路不需要标记图上有环路不标记就会无限递归。这道题的本质就是在二维网格图上做路径搜索标记必不可少。这三层能力是逐级嵌套的想到 DFS 是入门正确回溯是关键状态管理则是区分“背过模板”和“真正理解”的分水岭。1.3 为什么它是 Hot100 的常客这道题在面试里出现频率很高我觉得有三个原因。第一题目简短不涉及复杂的数据结构非常适合作为手写题在 45 分钟内考察。面试官可以从最简单的暴力枚举开始引导一步步看候选人能不能想到回溯属于“难度可控、区分度很高”的题。第二它特别容易暴露基本功。边界判断有没有先做、字符恢复的位置对不对、起始点遍历有没有漏两三分钟就能看出一个人的代码习惯和熟练度。第三它是一类题的地基。LeetCode 上不少题目是它的变形212 题单词搜索 II 要处理多个单词329 题矩阵中的最长递增路径本质是带记忆化的 DFS连 51 题 N 皇后、39 题组合总和这类经典回溯题核心的“状态管理”思路和它一模一样。2. 思路推演——从暴力枚举到回溯的完整链路2.1 为什么不能把所有路径都枚举出来最直接的想法枚举出 board 中所有可能的路径看能不能拼出 word。稍微算一下就知道不现实。每个格子出发最多有 4 个方向路径每延伸一步可能性乘 4路径长度为 L 时总路径数是 m * n * 4^L 数量级。假设 board 是 6x6word 长度是 154^15 大概是 10 亿量级这个规模根本枚举不完。而且这里面有大量的浪费很多路径在第二个字符就已经和 word[1] 不匹配了根本不用继续往下走。真正聪明的做法是边走边验证一旦发现当前字符不匹配立刻放弃这条分支。关键洞察是我们不是在找“所有路径”而是在找“一条能匹配 word 的路径”。搜索过程中只要发现当前路径已经不可能匹配了就应该立即放弃而不是等走到头才发现白走了。这个“发现不可能就立刻止损”的动作就是剪枝。2.2 递归天然适配“一条路走到黑”DFS 的核心是栈式扩展从起点出发选一个方向一直走下去不行再退回来选别的方向。这个“走到底再回头”的过程和递归的调用栈配合得非常完美——每次进入新的函数调用就是往深处走一层函数返回时就是退回到上层。所以用递归实现 DFS 是水到渠成的事。dfs(i, j, k)这个函数的语义可以定义为当前在board[i][j]已经匹配了 word 的前 k 个字符接下来要向四周寻找能匹配word[k]的格子。k 从 0 走到len(word)就算成功。这里有个容易混淆的细节有人用 k 表示“已经匹配了几个字符”有人用 k 表示“当前要匹配第几个字符”。两种写法都能 AC但建议初学者用前者写终止条件k len(word)更直观不容易搞混。如果你在写代码时经常被索引问题绕晕不妨直接在纸上画一个长度为 3 的单词把 k0、k1、k2、k3 的递归状态写出来理清每一步匹配的是哪个字符边界问题会清晰很多。2.3 回溯的三步曲尝试、递归、回退回溯可以总结成三个动作。尝试把当前格子标记为“已访问”表示它进入了当前路径。递归从当前格子向四个方向继续扩展。回退四个方向都试完还没找到答案说明以当前格子开头的这条路走不通。此时撤销当前格子的“已访问”标记让后续其他路径能重新使用这个格子。拿走迷宫类比你在每个路口撒一把沙子做标记防止走重复路。但回溯的迷宫更特殊——当你从一条死胡同退回分岔口换另一条路走时如果这条新路也要经过之前某个路口那把沙子的标记擦掉。这里的标记是临时性质的撤销动作是回溯的灵魂。为什么必须撤销假设从 (0,0) 出发探索了一条经过 (1,1) 的路失败了。退回后换一条新路这条新路可能也要经过 (1,1)。如果 (1,1) 的标记没擦掉新路就被堵死了搜索会漏掉正确答案。所以每一层递归返回时都要把自己加的标记恢复原样。3. 代码实现与逐行解读——两个版本的核心差异3.1 标准写法visited 数组版本class Solution: def exist(self, board: List[List[str]], word: str) - bool: m, n len(board), len(board[0]) visited [[False] * n for _ in range(m)] directions [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(i: int, j: int, k: int) - bool: # 1. 终止条件所有字符都匹配完 if k len(word): return True # 2. 越界检查 if i 0 or i m or j 0 or j n: return False # 3. 已访问过或字符不匹配剪掉 if visited[i][j] or board[i][j] ! word[k]: return False # 4. 标记当前格子已访问 visited[i][j] True # 5. 向四个方向扩展 for di, dj in directions: if dfs(i di, j dj, k 1): return True # 6. 四个方向都失败撤销标记 visited[i][j] False return False # 枚举所有起始格子 for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False这段代码的核心逻辑就 8 行左右。逐段解释一下。第 2 行的k len(word)是终止条件。注意它必须放在越界检查之前。为什么不先检查越界因为当 k 已经等于 len(word) 时i 和 j 可能是上一轮递归向越界方向多走一步产生的新坐标。如果先检查越界函数会直接返回 False但此时 word 已经全部匹配完正确答案应该是 True。所以终止条件要放在最前面。第 3 行的越界检查很关键。每次向上下左右扩展一格后新坐标可能超出 board 边界必须在访问board[i][j]之前先判断。Python 的列表索引如果是负数比如board[-1][0]不会报错而是访问最后一行这会造成非常隐蔽的 bug——看起来没越界实际上已经跑到了错误的格子上。第 4 行的visited[i][j] or board[i][j] ! word[k]把“已经走过的格子”和“字符不匹配”合并剪掉。这里的短路逻辑很有用先判断是否访问过省一次字符比较字符不匹配时也直接剪掉不用进入下一步递归。第 6 行把visited[i][j]恢复为 False。这句是回溯的核心。漏掉它后面其他起点或者其他路径需要使用这个格子时就被挡住了出现漏解。你可以自己做一个实验把第 6 行注释掉用board [[A,B],[C,D]]、word ABDC跑一下大概率会得到错误结果。3.2 空间优化版原地修改 board既然已经知道当前格子是board[i][j]而且会在返回前恢复可以直接把board[i][j]改成任意一个在 board 中不可能出现的字符作为临时标记。这样省掉了 m * n 的 visited 数组空间。class Solution: def exist(self, board: List[List[str]], word: str) - bool: m, n len(board), len(board[0]) def dfs(i: int, j: int, k: int) - bool: if k len(word): return True if i 0 or i m or j 0 or j n: return False if board[i][j] ! word[k]: return False tmp board[i][j] board[i][j] # # 原地标记 for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]: if dfs(i di, j dj, k 1): return True board[i][j] tmp # 恢复原字符 return False for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False这个版本的核心假设是 board 里的字符不包含#。LeetCode 上 board 输入只包含大小写英文字母所以用#是安全的。如果你自己造测试数据时 board 里可能有#就换成\0或者干脆用 visited 数组。这个细节隐藏在“为什么要选这个标记字符”里面试时主动提一句会加分。两个版本的时间复杂度一样都是 O(m * n * 4^L)L 是 word 长度。空间上 visited 数组版本是 O(m * n)原地标记版本递归深度为 L调用栈空间是 O(L)不计算额外数组的话是 O(1)。3.3 最容易写错的三个细节第一个终止条件和越界检查的顺序。前面已经强调过k len(word)必须在最前面。如果先检查越界word 匹配完但坐标恰好越界时会返回 False正确答案应该是 True。这个错误非常经典毕竟递归是“先进入下一层再判断条件”很多人在写递归的时候会不自觉地调整条件的顺序导致边界问题。第二个visited 的恢复要放在循环外面还是里面。答案是放在循环外面、return False之前。有人会把撤销写在 for 循环的每个分支里导致代码重复且容易漏。统一在四个方向都尝试完之后执行一次最干净也最保险。第三个起始点枚举的时机。注意主函数里对每个格子都调用了dfs(i, j, 0)。有一种错误写法是只从 (0,0) 开始 dfs找不到就换个起点但 visited 数组没有清空。正常回溯的话每个起点搜完 visited 应该全部恢复为 False。如果你发现某个起点搜完后 visited 不是全 False说明回溯代码写错了而不是要去手动清空数组。这个点理解之后你的代码就稳了一大半。4. 剪枝实测——哪些优化真能提速哪些只是自我感动4.1 字符频率预判O(m*n) 完成最强剪枝LeetCode 的单词搜索因为 board 和 word 都比较小不加剪枝也能过。但面试时能主动提剪枝会是不错的加分项。最实用的第一个剪枝是字符频率预判统计 word 中每个字符的数量如果某个字符在 word 中出现的次数大于在 board 中出现的次数直接返回 False。from collections import Counter word_counter Counter(word) board_counter Counter(.join(.join(row) for row in board)) if word_counter - board_counter: return False这里的word_counter - board_counter会得到“word 中比 board 多的那些字符”如果结果非空说明 board 里根本没有足够的字符去拼出 word直接返回 False。这个剪枝在极端情况下效果非常明显。比如 word 是AAAAA而 board 里只有两个 A那无论怎么搜索都不可能拼出来。一次 O(m*n) 的预判能省掉后续所有搜索。成本极低逻辑完全正确不会误伤答案。4.2 方向选择从分支少的端点开始搜还有一个进阶思路如果word[0]在 board 中出现的次数远多于word[-1]可以选择从最后一个字符开始反向搜索。原理不复杂word[0]出现越多可选的起点就越多搜索树的分支就越多反过来从出现次数少的末尾字符开始搜起点的数量急剧减少搜索空间就小了。这是回溯题通用的优化思路——优先从分支最少的端点开始搜索。我实测过一个极端 caseword 是AAAAAAABboard 里有大量 A 但只有一个 B 作为结尾。正向搜索需要枚举大量起点每次都沿着 A 的路径往下探反向搜索则在找到唯一的 B 之后只需要沿着 A 的路径反着走一遍速度提升非常明显。具体实现上可以在主函数里判断一下 word 首尾字符在 board 中的出现次数如果board_counter[word[0]] board_counter[word[-1]]就把 word 反转再搜索。注意反转后匹配逻辑不用改因为路径是可逆的——正向能拼出来反向也能拼出来。4.3 剪枝不是越多越好别破坏正确性剪枝要注意一件事必须保证逻辑绝对正确不能为了提速牺牲正确性。比如网上有人提过“当前格子剩余可走的步数不足以匹配 word 剩余部分时剪枝”但这个论断需要额外保证“每个格子只能走一次”的前提下剩余可走的格子数计算要非常小心否则很容易误剪。稳妥的做法只用字符频率预判这类逻辑上绝对正确的剪枝就够了。还有一点想提醒LeetCode 的评测 case 比较温和这些优化不一定在绝对时间上拉开多大差距。但面试时主动提“我先做了字符频率预判再根据首尾字符频率决定是否反向搜索”面试官会看到你对复杂度的理解和对边界场景的敏感度。这才是剪枝真正的价值所在——它不是给你省那几毫秒的而是展示你思维深度的。4.4 不同写法对比实现方式改动成本核心收益风险点无剪枝 visited 版本基础写法逻辑清晰适合学习无字符频率预判加 3-4 行极端 case 直接返回 False几乎无风险反向搜索中需判断首尾频率起点少时提速明显需注意反转逻辑原地标记 board低省 O(m*n) 空间标记字符可能与 board 冲突5. 举一反三——从单词搜索到一整类回溯题5.1 单词搜索 II多加一棵 Trie 树LeetCode 212 题单词搜索 II给的是一组 words要求返回所有能在 board 中找到的单词。如果对每个单词单独跑一遍单词搜索的 DFSwords 很多时效率非常低。经典解法是把所有 words 插入一棵 Trie字典树然后在 board 上做 DFS。每到一步都判断当前路径字符组成的字符串是不是某个单词的前缀。如果是继续扩展如果不是剪枝如果到达某个单词的结尾就记录下来。Trie 在这里充当的就是“公共前缀剪枝器”。回溯的思想没变区别只是匹配目标从单个 word 变成了共享前缀。掌握单词搜索之后再看单词搜索 II难点其实只剩 Trie 的构建和遍历回溯部分反而是熟悉的套路。5.2 和岛屿类题目的一字之差LeetCode 上还有大量岛屿类题目比如 200 题岛屿数量、130 题被围绕的区域。它们也用 DFS但有一个关键区别岛屿类题目不需要回溯只需要遍历。因为岛屿题的目标是“把整块连通的区域标记出来”一旦一个格子被标记为已访问就再也不会被撤销而单词搜索的目标是“找一条匹配的路径”一个格子当前路径失败后可能在另一条路径里会被再次用到。这个区别可以总结成一句话需要找一条路径的用回溯需要找所有连通块的用普通 DFS 或 BFS。判断标准就是看“这个格子被访问标记后以后还有没有必要再被访问”。如果没必要说明是一锤子买卖的连通性问题如果有必要说明是路径探索问题需要完整的回溯机制。5.3 一套能迁移的通用回溯模板把单词搜索的精髓抽成模板可以适配很多路径搜索类回溯题def backtrack(状态, 匹配深度k): if k 目标长度: return True for 每个相邻状态: if 状态不合法: continue 做状态修改 if backtrack(新状态, k 1): return True 撤销状态修改 return FalseN 皇后问题里用 col 数组标记哪些列被占用这就是“做状态修改/撤销修改”的具体化组合总和问题里用 startIndex 控制可选集合的范围本质上也是回溯。状态管理的方式不同但骨架完全一致。个人经验是刷题不用贪多。把单词搜索这一道题吃透到“能闭眼写出、能给面试官讲清楚每一步为什么”的程度比囫囵吞枣做十道更有效。面试时如果遇到回溯题思路会非常顺畅因为底层的“状态管理”这一关你已经彻底过了。最后分享一个我刷这道题的体会第一次 AC 之后别急着做下一题。试着把 visited 数组改成原地标记再写一遍改完再试着手写一个非递归的栈版本不用系统递归。这几步折腾下来你对“递归调用栈”和“回溯状态恢复”的理解会上一个台阶。LeetCode Hot100 里回溯章节的题不少但绝大多数核心思想都能在 79 题里找到源头。