尧图网站建设 
最近集中刷 LeetCode 热题 100刷到第 79 题“单词搜索”的时候我停下来多看了几眼。原因很简单这道题排在中等难度但它在面试里的出场频率一点不比那些 hard 题低。二维网格、DFS、回溯、状态恢复这几个关键词只要你能答全面试官基本就会点头认可。更重要的是它是理解回溯算法的绝佳样本——很多人卡在这题不是因为代码不会写而是没想明白“为什么递归返回之后必须恢复现场”。这篇文章我就以自己从读题到 AC 的完整过程为线索把单词搜索前前后后拆开讲透。内容包括题目到底在考什么、DFS 与回溯的关系、三种语言的完整实现、三个高频优化点以及一个含金量很高的扩展——LeetCode 212“单词搜索 II”的 Trie 解法。适合正在刷热题 100 准备面试、或者想系统搞懂 DFS 回溯的朋友照着文章思路走一遍比闷头刷十道类似题效率高。1. 题目定位与考点分析1.1 表面考字符串匹配实际考递归状态管理先看原题描述给你一个 m×n 的二维字符网格 board 和一个字符串 word判断 word 是否存在于网格里。规则是单词必须按字母顺序、通过相邻单元格内的字母构成而每个单元格在搜索路径中只能用一次。很多人第一眼觉得这是字符串匹配题想用哈希表记录每个字符出现的位置再按单词顺序拼接路径。这个思路在单个字符独立时可以成立但一旦加上“相邻单元格”和“每个单元格只能使用一次”这两个条件就成了典型的图搜索问题。而图搜索问题里判断“是否存在一条满足条件的路径”DFS 是直觉最强的工具从某个起点出发沿着匹配的方向一直走下去走不通就回退。这里我特别想强调“每个单元格只能用一次”这条约束。它决定了这题不能贪心也不能用简单的多源遍历。在实际搜索过程中某条路径可能试探到一半发现方向全被占用此时必须“撤销”刚才的占用标记换一个分支继续。这个撤销动作就是回溯的核心。拿官方的简单样例来推演能看得很清楚。假设棋盘长这样A B C E S F C S A D E E要查找的单词是ABCCED。从(0,0)的 A 出发往下走是 S不匹配往右走是 B匹配。接着 B 的右边是 C匹配C 的下面也是 C匹配再往下是 E匹配最后左边是 D匹配整条路径走通。可如果走的过程中遇到死胡同比如在某一步四个方向要么越界、要么字符不匹配、要么格子已用过就必须回到上一个格子尝试其他方向。这个过程用递归写最自然。约 530 字1.2 热题 100 里它常青的原因为什么单词搜索在热题 100 里一直稳坐位置我觉得它把回溯算法的所有要素压缩进了一个中等题里决策每一步向上下左右四个方向扩展约束下一个字符必须匹配不能走出网格不能重复使用单元格目标匹配到 word 的最后一个字符状态恢复回退时取消单元格占用标记。这四点合起来就是标准回溯模板。把模板吃透之后再去刷热题 100 里的全排列、子集、组合总和你会发现骨架完全一样变的只是决策和约束条件。这也是为什么很多人建议把单词搜索当成回溯“入门必写题”反复写三五遍都不嫌多写到不用思考就能默写出框架为止。约 320 字2. 核心思路拆解与算法选型2.1 DFS、BFS 与预处理方案对比先说结论这题的主流传法就是 DFS 回溯没有之一。我见过有人尝试 BFS理由是“找路径用 BFS 更稳”但实际跑起来非常别扭。我们对比一下三种常见思路方案空间复杂度状态管理适用性BFSO(mn) 以上每层需复制路径占用状态每一层都要记录“哪些格子已用”扩展时复制整条路径能解但代码复杂、开销大DFS 回溯递归栈 O(mn)配合原地标记 O(1) 额外空间只维护当前路径链上的占用标记回退时恢复最自然代码最简洁字符哈希预处理O(mn) 存储无法表达“相邻”约束只能做前置过滤不能独立解题只能配合BFS 的问题在于它按层扩展每一层的每个节点都需要携带一份“历史路径占用表”。在网格稍大的时候复制开销非常夸张。DFS 则沿着一条链深入只要在递归进入前打标记、返回后撤销就能用 O(1) 的额外空间完成去重。这也是为什么所有公开题解都默认 DFS。约 330 字含表格2.2 递归函数的语义设计写 DFS 之前先把递归函数设计清楚这是代码正确性的地基。我习惯这样定义dfs(x, y, k)表示“从网格的 (x, y) 出发能否匹配 word 中从索引 k 开始的剩余字符”。这个定义里x、y 是当前位置k 是已经匹配的字符数量也是 word 的下标。不需要额外维护一个 path 列表保存走过的字符因为单词的顺序完全由 k 决定board[x][y]必须等于word[k]然后递归去匹配word[k1]。递归的终止条件有三个当前位置字符不匹配返回 False当前位置字符匹配且 k 已经是 word 的最后一个字符说明整条路径全部匹配成功返回 True当前位置字符匹配但还没到末尾则标记占用并尝试四个方向。还有一个隐含的终止条件四个方向都尝试失败后撤销标记并返回 False。用这样的语义设计函数签名小而清晰状态全靠 (x, y, k) 三元组推动恢复现场只需要一行代码。比“把整条路径塞进参数”的设计要健壮得多。约 420 字3. 完整实现与三个关键优化3.1 基础版实现Python / Java / C 三连先给最朴素的版本。虽然朴素但已经能在 LeetCode 上 AC因为 m、n 最多 6word 最长 15暴力回溯完全够用。Pythonclass Solution: def exist(self, board: List[List[str]], word: str) - bool: m, n len(board), len(board[0]) dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(x: int, y: int, k: int) - bool: if board[x][y] ! word[k]: return False if k len(word) - 1: return True board[x][y] # # 占用标记用特殊字符代替 visited 数组 for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n: if dfs(nx, ny, k 1): return True board[x][y] word[k] # 回溯恢复现场 return False for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False为什么可以用字符#代替 visited 数组因为 board 里原有的元素是大小写字母#不可能出现在原网格里。标记成#后后续递归访问到该格子时board[nx][ny] ! word[k]会立即判断失败等价于“已访问过”。这个技巧省掉了一个 m×n 的布尔数组而且状态恢复只需把原字符写回非常干净。Java 版本class Solution { private int m, n; private char[][] board; private String word; private int[] dx {1, -1, 0, 0}; private int[] dy {0, 0, 1, -1}; public boolean exist(char[][] board, String word) { this.m board.length; this.n board[0].length; this.board board; this.word word; for (int i 0; i m; i) { for (int j 0; j n; j) { if (dfs(i, j, 0)) return true; } } return false; } private boolean dfs(int x, int y, int k) { if (board[x][y] ! word.charAt(k)) return false; if (k word.length() - 1) return true; board[x][y] #; for (int d 0; d 4; d) { int nx x dx[d], ny y dy[d]; if (nx 0 nx m ny 0 ny n dfs(nx, ny, k 1)) { return true; } } board[x][y] word.charAt(k); return false; } }C 版本class Solution { public: bool exist(vectorvectorchar board, string word) { m board.size(); n board[0].size(); for (int i 0; i m; i) { for (int j 0; j n; j) { if (dfs(board, word, i, j, 0)) return true; } } return false; } private: int m, n; int dirs[4][2] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; bool dfs(vectorvectorchar board, const string word, int x, int y, int k) { if (board[x][y] ! word[k]) return false; if (k word.size() - 1) return true; board[x][y] #; for (auto d : dirs) { int nx x d[0], ny y d[1]; if (nx 0 nx m ny 0 ny n dfs(board, word, nx, ny, k 1)) { return true; } } board[x][y] word[k]; return false; } };三个版本的核心逻辑完全一致差异只在语言语法。面试时通常更推荐 Java 或 C因为用 Python 面试容易在递归深度和性能上被追问虽然不是大问题但准备充分一点总没错。约 620 字含大段代码3.2 优化一字符频次预判真正的优化顺序我会把“字符频次预判”放第一位。原因是它不仅能提升速度还能处理一个边界 case。在进入主循环之前统计 board 中每个字符出现的次数再统计 word 中每个字符出现的次数。如果 word 中某个字符的次数大于 board 中的次数直接返回 False。from collections import Counter # 统计 board 中全部字符 board_chars Counter(.join(.join(row) for row in board)) # 统计 word 中字符 word_chars Counter(word) # 如果 word 中存在某字符数量超过 board 的提供能力直接判 false if word_chars - board_chars: return FalsePython 里用 Counter 做差集左边如果还有剩余说明 word 中含有 board 根本不存在的字符或数量不够。这一步在 word 比较长、网格比较小的时候能提前剪掉大量无意义搜索比如 word aaaaaa...a15 个 a、网格里只有一个 a 的情况一秒都不用跑就知道答案。这行判断面试时能加就加属于“虽然不改变最坏复杂度但能体现细节意识”的加分操作。约 410 字3.3 优化二搜索起点与方向顺序剪枝起点选择很关键。多数人的第一版代码是从网格每个位置开始搜索这没问题但对于 word 首字符大量出现在网格角落的 case搜索量会显著增加。一个直观的优化反向搜索。当 word 首字符在 board 中出现次数多于末字符时从后往前匹配即从 word 的最后一个字符开始做 DFS。原理很简单DFS 的递归树深度和分支数由匹配起点决定起点字符越稀有候选起点越少整体搜索规模越小。具体做法比较word[0]和word[-1]在 board 中出现的次数如果word[0]出现次数更多就把 word 反转再跑同一个 DFS。LeetCode 官方题解也提到了类似策略在极端构造数据上能把耗时从 90ms 压到 10ms 以内实战效果很香。约 330 字3.4 优化三方向遍历顺序与边界检查最后一个优化点很小但很实用遍历四个方向的顺序可以按“下一步字符出现的可能性”排序。比如把方向数组调整成上、下、左、右并不会改变正确性但有些 case 中按特定顺序能更快命中答案。更讲道理的做法是在递归前根据当前字符附近哪个方向最可能匹配word[k1]动态调整方向顺序。不过对本题数据规模来说方向顺序的影响远不如起点反转大我一般把它当成“锦上添花”来加不会在面试里主动提除非面试官追问。真正需要重视的是“先检查边界再递归”的顺序先算 nx、ny判断是否在网格内再进入递归不要进入递归后再判断数组越界否则会抛异常或读到脏数据。这个顺序在三种语言里都一样属于基础素养。约 280 字4. 扩展从单词搜索到单词搜索 II4.1 一次搜多个单词时朴素 DFS 为什么不行热题 100 里只有单单词版本的单词搜索但面试官很爱在追问环节把它升级成 LeetCode 212“单词搜索 II”给定一个网格和一组单词返回所有能在网格中找到的单词。如果沿用朴素 DFS每个单词都跑一遍完整的网格遍历时间复杂度直接变成 O(单词数 × m×n×4^len)。假设有 50 个单词、网格 12×12这个量级在 LeetCode 上基本会超时。更致命的浪费在于多个单词之间存在公共前缀。比如 words [oath, oat, oak]前三个字母一样分开搜索时同样的路径被重复跑三遍。能用一次遍历同时探索所有单词的结构就是字典树 Trie。约 330 字4.2 Trie DFS 的经典组合思路分成两步。第一步把所有单词插入一棵 Trie。Trie 的每个节点用一个布尔标记isEnd表示“是否有单词在这里结束”也可以用word字段直接存储完整单词方便返回答案时不回溯拼接。第二步在网格上做 DFS。此时 DFS 的参数从 k单词索引变成 node当前 Trie 节点。每走一步就看board[x][y]是否在 node 的子节点中如果在就继续深入如果 node 恰好是某个单词的结尾就把这个单词加入答案。Python 实现参考class TrieNode: def __init__(self): self.children {} self.word None # 存储完整单词省去回溯拼接 class Solution: def findWords(self, board: List[List[str]], words: List[str]) - List[str]: root TrieNode() for w in words: node root for ch in w: if ch not in node.children: node.children[ch] TrieNode() node node.children[ch] node.word w m, n len(board), len(board[0]) res set() dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(x: int, y: int, node: TrieNode) - None: ch board[x][y] if ch not in node.children: return nxt node.children[ch] if nxt.word is not None: res.add(nxt.word) board[x][y] # for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n: dfs(nx, ny, nxt) board[x][y] ch # 可选的 Trie 剪枝如果 nxt 没有子节点可以删掉 if not nxt.children: node.children.pop(ch) for i in range(m): for j in range(n): dfs(i, j, root) return list(res)注意最后那个“删除无子节点”的剪枝。当 nxt 没有子节点时它只可能是某个单词的终点而这个单词已经被记录过了后续不可能再有新单词路过这里所以可以直接从父节点移除。这个剪枝叫“Trie 树剪枝”在单词数量大的 case 里能显著降低重复访问。约 560 字含大段代码4.3 复杂度变化与面试加分点单词搜索 II 的时间复杂度分析比第一题复杂。最坏情况下是 O(m×n×4^(m×n)) 的指数级但因为 Trie 把大量单词压缩在同一个搜索树里实际运行远快于朴素解法。空间复杂度方面Trie 的节点数线性于所有单词总长度加上 DFS 递归栈的 O(L)。面试时能讲清楚“为什么用 Trie”是核心加分点因为回溯搜索的瓶颈在于重复探索公共前缀而 Trie 天然把前缀去重搜索同一棵树相当于同时进行多个单词的回溯互相抵消无效分支。很多候选人都能写出 findWords 的代码但说不出这一句面试官对深度的评价会差整整一档。约 290 字5. 常见问题与排查技巧实录5.1 回溯忘了恢复现场是最高频的 bug刷题社区里单词搜索的求助帖十有八九是这个问题“为什么我搜出来的路径重复使用了同一个格子”看代码会发现递归返回后没有把board[x][y] word[k]写回去。结果是一条路径失败后格子永远是#后续从别的起点出发时明明可以走的格子被误判为已占用导致正确答案搜不到。排查方法在递归函数开头打印当前路径和 k或者把 board 的变化打印出来一跑样例就露馅。真正到了面试里口述时一定要把“恢复现场”四个字说出来因为它正是回溯算法的灵魂。约 280 字5.2 递归边界的三个坑第一个坑是数组越界。四个方向扩展时必须先判断 nx、ny 是否在 [0, m) 和 [0, n) 范围内再访问board[nx][ny]。把判断顺序写反在小数据上偶尔能过但在边界 case 下会直接抛 ArrayIndexOutOfBoundsException。第二个坑是 k 的终止条件。有人写成if k len(word)然后去访问word[k]导致 IndexError。正确写法是先判断board[x][y] ! word[k]再判断k len(word) - 1。这两个判断的顺序不能换如果先判断后者k 越界后再去访问word[k]就崩了。第三个坑是方向数组写错。常见的错误是把 (1,0)、(-1,0)、(0,1)、(0,-1) 写成 (1,0)、(0,1)、(-1,0)、(0,-1)有人会多写一个 (0,0)。看起来没影响但 (0,0) 会让递归原地打转直接栈溢出。约 330 字5.3 面试官可能追问的变体我整理了几个常见升级方向变体思路网格很大单词很长如何提速字符频次预判 起点反转 Trie多单词场景要求输出找到的路径而不是只判断是否存在dfs 增加 path 参数记录坐标序列终止时保存副本单词可以走斜对角dirs 扩成 8 个方向边界判断不变同一个单词在网格中出现多次需要去重多单词版用 set 去重单单词版返回第一个 True 即可网格中同时存在多个单词且要求按字典序输出Trie DFS res.sort()这些问题都不难关键是“知道变体对应的核心变化点”。比如斜对角只是方向数组从 4 变 8其他逻辑完全不动答案脱口而出会显得基础很扎实。约 320 字5.4 一个全真调试小技巧用小样例手推状态除了看代码我强烈建议在本地把样例缩小到 2×2 或 3×3然后手动走一遍递归。拿board [[A,B],[C,D]]、word ABDC来说从 (0,0) 的 A 出发匹配 B 后向右走再匹配 D 后向下走最后匹配 C。走到 D 时(0,0) 已经标记为#只有 (1,0) 的 C 没被占用路径是唯一确定的。这种小样例手动推一遍比在 LeetCode 上反复提交试错快得多。推完之后再检查代码里每一步标记、恢复写的位置基本能定位 90% 的问题。我刷热题 100 时养成的习惯是凡是回溯题先推一个最小 case再写代码AC 率会明显提升。约 300 字6. 刷题中的实战体会与举一反三6.1 热题 100 里和回溯强相关的题目怎么串联刷完单词搜索我建议趁热把热题 100 里的回溯题按顺序过一遍全排列、子集、组合总和、括号生成。它们的共同模板都是backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择单词搜索的特殊之处只在于“选择列表”不是固定的数组而是当前格子的上下左右。把这一点想明白DFS 回溯题在你眼里就不再是几十道孤立题目而是一套可以套用的思维框架。我在刷这组题时会刻意用同一个模板去写每道题的代码框架只有决策和约束部分不同后面再遇到新题写起来非常快。约 300 字6.2 实际做题时我的几个习惯最后分享两个我自己常用的实操技巧。一是先写“伪代码酒精测试”。真正动键盘前用伪代码把 dfs 的参数、返回条件、标记、恢复四步写全对着 word 的例子手动走一遍。这一步能挡掉至少一半的边界错误尤其适合新手。二是善用 LeetCode 的“相关题目”功能。做完单词搜索后把单词搜索 II、被围绕的区域、岛屿数量这些网格题放在同一天做。网格 DFS 的套路是共通的连续做三四道之后边界条件、方向数组、visited 标记这些动作会变成肌肉记忆后续再遇到类似题能省很多时间。如果你正在刷热题 100我的建议是不要追求一天刷很多道而是在每一道经典题上把“为什么这么做”想透。单词搜索这道题配合二分查找那类比如著名的吃香蕉问题交替练习一天两题、坚持一个月效果比我刚刷题时那种贪快乱刷好得多。我自己后来回看刷题记录真正留下印象、面试时能马上迁移的就是那些认真拆解过思路的中等题。 LeetCode单词搜索拆解：DFS回溯、状态恢复与Trie优化
最近集中刷 LeetCode 热题 100刷到第 79 题“单词搜索”的时候我停下来多看了几眼。原因很简单这道题排在中等难度但它在面试里的出场频率一点不比那些 hard 题低。二维网格、DFS、回溯、状态恢复这几个关键词只要你能答全面试官基本就会点头认可。更重要的是它是理解回溯算法的绝佳样本——很多人卡在这题不是因为代码不会写而是没想明白“为什么递归返回之后必须恢复现场”。这篇文章我就以自己从读题到 AC 的完整过程为线索把单词搜索前前后后拆开讲透。内容包括题目到底在考什么、DFS 与回溯的关系、三种语言的完整实现、三个高频优化点以及一个含金量很高的扩展——LeetCode 212“单词搜索 II”的 Trie 解法。适合正在刷热题 100 准备面试、或者想系统搞懂 DFS 回溯的朋友照着文章思路走一遍比闷头刷十道类似题效率高。1. 题目定位与考点分析1.1 表面考字符串匹配实际考递归状态管理先看原题描述给你一个 m×n 的二维字符网格 board 和一个字符串 word判断 word 是否存在于网格里。规则是单词必须按字母顺序、通过相邻单元格内的字母构成而每个单元格在搜索路径中只能用一次。很多人第一眼觉得这是字符串匹配题想用哈希表记录每个字符出现的位置再按单词顺序拼接路径。这个思路在单个字符独立时可以成立但一旦加上“相邻单元格”和“每个单元格只能使用一次”这两个条件就成了典型的图搜索问题。而图搜索问题里判断“是否存在一条满足条件的路径”DFS 是直觉最强的工具从某个起点出发沿着匹配的方向一直走下去走不通就回退。这里我特别想强调“每个单元格只能用一次”这条约束。它决定了这题不能贪心也不能用简单的多源遍历。在实际搜索过程中某条路径可能试探到一半发现方向全被占用此时必须“撤销”刚才的占用标记换一个分支继续。这个撤销动作就是回溯的核心。拿官方的简单样例来推演能看得很清楚。假设棋盘长这样A B C E S F C S A D E E要查找的单词是ABCCED。从(0,0)的 A 出发往下走是 S不匹配往右走是 B匹配。接着 B 的右边是 C匹配C 的下面也是 C匹配再往下是 E匹配最后左边是 D匹配整条路径走通。可如果走的过程中遇到死胡同比如在某一步四个方向要么越界、要么字符不匹配、要么格子已用过就必须回到上一个格子尝试其他方向。这个过程用递归写最自然。约 530 字1.2 热题 100 里它常青的原因为什么单词搜索在热题 100 里一直稳坐位置我觉得它把回溯算法的所有要素压缩进了一个中等题里决策每一步向上下左右四个方向扩展约束下一个字符必须匹配不能走出网格不能重复使用单元格目标匹配到 word 的最后一个字符状态恢复回退时取消单元格占用标记。这四点合起来就是标准回溯模板。把模板吃透之后再去刷热题 100 里的全排列、子集、组合总和你会发现骨架完全一样变的只是决策和约束条件。这也是为什么很多人建议把单词搜索当成回溯“入门必写题”反复写三五遍都不嫌多写到不用思考就能默写出框架为止。约 320 字2. 核心思路拆解与算法选型2.1 DFS、BFS 与预处理方案对比先说结论这题的主流传法就是 DFS 回溯没有之一。我见过有人尝试 BFS理由是“找路径用 BFS 更稳”但实际跑起来非常别扭。我们对比一下三种常见思路方案空间复杂度状态管理适用性BFSO(mn) 以上每层需复制路径占用状态每一层都要记录“哪些格子已用”扩展时复制整条路径能解但代码复杂、开销大DFS 回溯递归栈 O(mn)配合原地标记 O(1) 额外空间只维护当前路径链上的占用标记回退时恢复最自然代码最简洁字符哈希预处理O(mn) 存储无法表达“相邻”约束只能做前置过滤不能独立解题只能配合BFS 的问题在于它按层扩展每一层的每个节点都需要携带一份“历史路径占用表”。在网格稍大的时候复制开销非常夸张。DFS 则沿着一条链深入只要在递归进入前打标记、返回后撤销就能用 O(1) 的额外空间完成去重。这也是为什么所有公开题解都默认 DFS。约 330 字含表格2.2 递归函数的语义设计写 DFS 之前先把递归函数设计清楚这是代码正确性的地基。我习惯这样定义dfs(x, y, k)表示“从网格的 (x, y) 出发能否匹配 word 中从索引 k 开始的剩余字符”。这个定义里x、y 是当前位置k 是已经匹配的字符数量也是 word 的下标。不需要额外维护一个 path 列表保存走过的字符因为单词的顺序完全由 k 决定board[x][y]必须等于word[k]然后递归去匹配word[k1]。递归的终止条件有三个当前位置字符不匹配返回 False当前位置字符匹配且 k 已经是 word 的最后一个字符说明整条路径全部匹配成功返回 True当前位置字符匹配但还没到末尾则标记占用并尝试四个方向。还有一个隐含的终止条件四个方向都尝试失败后撤销标记并返回 False。用这样的语义设计函数签名小而清晰状态全靠 (x, y, k) 三元组推动恢复现场只需要一行代码。比“把整条路径塞进参数”的设计要健壮得多。约 420 字3. 完整实现与三个关键优化3.1 基础版实现Python / Java / C 三连先给最朴素的版本。虽然朴素但已经能在 LeetCode 上 AC因为 m、n 最多 6word 最长 15暴力回溯完全够用。Pythonclass Solution: def exist(self, board: List[List[str]], word: str) - bool: m, n len(board), len(board[0]) dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(x: int, y: int, k: int) - bool: if board[x][y] ! word[k]: return False if k len(word) - 1: return True board[x][y] # # 占用标记用特殊字符代替 visited 数组 for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n: if dfs(nx, ny, k 1): return True board[x][y] word[k] # 回溯恢复现场 return False for i in range(m): for j in range(n): if dfs(i, j, 0): return True return False为什么可以用字符#代替 visited 数组因为 board 里原有的元素是大小写字母#不可能出现在原网格里。标记成#后后续递归访问到该格子时board[nx][ny] ! word[k]会立即判断失败等价于“已访问过”。这个技巧省掉了一个 m×n 的布尔数组而且状态恢复只需把原字符写回非常干净。Java 版本class Solution { private int m, n; private char[][] board; private String word; private int[] dx {1, -1, 0, 0}; private int[] dy {0, 0, 1, -1}; public boolean exist(char[][] board, String word) { this.m board.length; this.n board[0].length; this.board board; this.word word; for (int i 0; i m; i) { for (int j 0; j n; j) { if (dfs(i, j, 0)) return true; } } return false; } private boolean dfs(int x, int y, int k) { if (board[x][y] ! word.charAt(k)) return false; if (k word.length() - 1) return true; board[x][y] #; for (int d 0; d 4; d) { int nx x dx[d], ny y dy[d]; if (nx 0 nx m ny 0 ny n dfs(nx, ny, k 1)) { return true; } } board[x][y] word.charAt(k); return false; } }C 版本class Solution { public: bool exist(vectorvectorchar board, string word) { m board.size(); n board[0].size(); for (int i 0; i m; i) { for (int j 0; j n; j) { if (dfs(board, word, i, j, 0)) return true; } } return false; } private: int m, n; int dirs[4][2] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; bool dfs(vectorvectorchar board, const string word, int x, int y, int k) { if (board[x][y] ! word[k]) return false; if (k word.size() - 1) return true; board[x][y] #; for (auto d : dirs) { int nx x d[0], ny y d[1]; if (nx 0 nx m ny 0 ny n dfs(board, word, nx, ny, k 1)) { return true; } } board[x][y] word[k]; return false; } };三个版本的核心逻辑完全一致差异只在语言语法。面试时通常更推荐 Java 或 C因为用 Python 面试容易在递归深度和性能上被追问虽然不是大问题但准备充分一点总没错。约 620 字含大段代码3.2 优化一字符频次预判真正的优化顺序我会把“字符频次预判”放第一位。原因是它不仅能提升速度还能处理一个边界 case。在进入主循环之前统计 board 中每个字符出现的次数再统计 word 中每个字符出现的次数。如果 word 中某个字符的次数大于 board 中的次数直接返回 False。from collections import Counter # 统计 board 中全部字符 board_chars Counter(.join(.join(row) for row in board)) # 统计 word 中字符 word_chars Counter(word) # 如果 word 中存在某字符数量超过 board 的提供能力直接判 false if word_chars - board_chars: return FalsePython 里用 Counter 做差集左边如果还有剩余说明 word 中含有 board 根本不存在的字符或数量不够。这一步在 word 比较长、网格比较小的时候能提前剪掉大量无意义搜索比如 word aaaaaa...a15 个 a、网格里只有一个 a 的情况一秒都不用跑就知道答案。这行判断面试时能加就加属于“虽然不改变最坏复杂度但能体现细节意识”的加分操作。约 410 字3.3 优化二搜索起点与方向顺序剪枝起点选择很关键。多数人的第一版代码是从网格每个位置开始搜索这没问题但对于 word 首字符大量出现在网格角落的 case搜索量会显著增加。一个直观的优化反向搜索。当 word 首字符在 board 中出现次数多于末字符时从后往前匹配即从 word 的最后一个字符开始做 DFS。原理很简单DFS 的递归树深度和分支数由匹配起点决定起点字符越稀有候选起点越少整体搜索规模越小。具体做法比较word[0]和word[-1]在 board 中出现的次数如果word[0]出现次数更多就把 word 反转再跑同一个 DFS。LeetCode 官方题解也提到了类似策略在极端构造数据上能把耗时从 90ms 压到 10ms 以内实战效果很香。约 330 字3.4 优化三方向遍历顺序与边界检查最后一个优化点很小但很实用遍历四个方向的顺序可以按“下一步字符出现的可能性”排序。比如把方向数组调整成上、下、左、右并不会改变正确性但有些 case 中按特定顺序能更快命中答案。更讲道理的做法是在递归前根据当前字符附近哪个方向最可能匹配word[k1]动态调整方向顺序。不过对本题数据规模来说方向顺序的影响远不如起点反转大我一般把它当成“锦上添花”来加不会在面试里主动提除非面试官追问。真正需要重视的是“先检查边界再递归”的顺序先算 nx、ny判断是否在网格内再进入递归不要进入递归后再判断数组越界否则会抛异常或读到脏数据。这个顺序在三种语言里都一样属于基础素养。约 280 字4. 扩展从单词搜索到单词搜索 II4.1 一次搜多个单词时朴素 DFS 为什么不行热题 100 里只有单单词版本的单词搜索但面试官很爱在追问环节把它升级成 LeetCode 212“单词搜索 II”给定一个网格和一组单词返回所有能在网格中找到的单词。如果沿用朴素 DFS每个单词都跑一遍完整的网格遍历时间复杂度直接变成 O(单词数 × m×n×4^len)。假设有 50 个单词、网格 12×12这个量级在 LeetCode 上基本会超时。更致命的浪费在于多个单词之间存在公共前缀。比如 words [oath, oat, oak]前三个字母一样分开搜索时同样的路径被重复跑三遍。能用一次遍历同时探索所有单词的结构就是字典树 Trie。约 330 字4.2 Trie DFS 的经典组合思路分成两步。第一步把所有单词插入一棵 Trie。Trie 的每个节点用一个布尔标记isEnd表示“是否有单词在这里结束”也可以用word字段直接存储完整单词方便返回答案时不回溯拼接。第二步在网格上做 DFS。此时 DFS 的参数从 k单词索引变成 node当前 Trie 节点。每走一步就看board[x][y]是否在 node 的子节点中如果在就继续深入如果 node 恰好是某个单词的结尾就把这个单词加入答案。Python 实现参考class TrieNode: def __init__(self): self.children {} self.word None # 存储完整单词省去回溯拼接 class Solution: def findWords(self, board: List[List[str]], words: List[str]) - List[str]: root TrieNode() for w in words: node root for ch in w: if ch not in node.children: node.children[ch] TrieNode() node node.children[ch] node.word w m, n len(board), len(board[0]) res set() dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(x: int, y: int, node: TrieNode) - None: ch board[x][y] if ch not in node.children: return nxt node.children[ch] if nxt.word is not None: res.add(nxt.word) board[x][y] # for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n: dfs(nx, ny, nxt) board[x][y] ch # 可选的 Trie 剪枝如果 nxt 没有子节点可以删掉 if not nxt.children: node.children.pop(ch) for i in range(m): for j in range(n): dfs(i, j, root) return list(res)注意最后那个“删除无子节点”的剪枝。当 nxt 没有子节点时它只可能是某个单词的终点而这个单词已经被记录过了后续不可能再有新单词路过这里所以可以直接从父节点移除。这个剪枝叫“Trie 树剪枝”在单词数量大的 case 里能显著降低重复访问。约 560 字含大段代码4.3 复杂度变化与面试加分点单词搜索 II 的时间复杂度分析比第一题复杂。最坏情况下是 O(m×n×4^(m×n)) 的指数级但因为 Trie 把大量单词压缩在同一个搜索树里实际运行远快于朴素解法。空间复杂度方面Trie 的节点数线性于所有单词总长度加上 DFS 递归栈的 O(L)。面试时能讲清楚“为什么用 Trie”是核心加分点因为回溯搜索的瓶颈在于重复探索公共前缀而 Trie 天然把前缀去重搜索同一棵树相当于同时进行多个单词的回溯互相抵消无效分支。很多候选人都能写出 findWords 的代码但说不出这一句面试官对深度的评价会差整整一档。约 290 字5. 常见问题与排查技巧实录5.1 回溯忘了恢复现场是最高频的 bug刷题社区里单词搜索的求助帖十有八九是这个问题“为什么我搜出来的路径重复使用了同一个格子”看代码会发现递归返回后没有把board[x][y] word[k]写回去。结果是一条路径失败后格子永远是#后续从别的起点出发时明明可以走的格子被误判为已占用导致正确答案搜不到。排查方法在递归函数开头打印当前路径和 k或者把 board 的变化打印出来一跑样例就露馅。真正到了面试里口述时一定要把“恢复现场”四个字说出来因为它正是回溯算法的灵魂。约 280 字5.2 递归边界的三个坑第一个坑是数组越界。四个方向扩展时必须先判断 nx、ny 是否在 [0, m) 和 [0, n) 范围内再访问board[nx][ny]。把判断顺序写反在小数据上偶尔能过但在边界 case 下会直接抛 ArrayIndexOutOfBoundsException。第二个坑是 k 的终止条件。有人写成if k len(word)然后去访问word[k]导致 IndexError。正确写法是先判断board[x][y] ! word[k]再判断k len(word) - 1。这两个判断的顺序不能换如果先判断后者k 越界后再去访问word[k]就崩了。第三个坑是方向数组写错。常见的错误是把 (1,0)、(-1,0)、(0,1)、(0,-1) 写成 (1,0)、(0,1)、(-1,0)、(0,-1)有人会多写一个 (0,0)。看起来没影响但 (0,0) 会让递归原地打转直接栈溢出。约 330 字5.3 面试官可能追问的变体我整理了几个常见升级方向变体思路网格很大单词很长如何提速字符频次预判 起点反转 Trie多单词场景要求输出找到的路径而不是只判断是否存在dfs 增加 path 参数记录坐标序列终止时保存副本单词可以走斜对角dirs 扩成 8 个方向边界判断不变同一个单词在网格中出现多次需要去重多单词版用 set 去重单单词版返回第一个 True 即可网格中同时存在多个单词且要求按字典序输出Trie DFS res.sort()这些问题都不难关键是“知道变体对应的核心变化点”。比如斜对角只是方向数组从 4 变 8其他逻辑完全不动答案脱口而出会显得基础很扎实。约 320 字5.4 一个全真调试小技巧用小样例手推状态除了看代码我强烈建议在本地把样例缩小到 2×2 或 3×3然后手动走一遍递归。拿board [[A,B],[C,D]]、word ABDC来说从 (0,0) 的 A 出发匹配 B 后向右走再匹配 D 后向下走最后匹配 C。走到 D 时(0,0) 已经标记为#只有 (1,0) 的 C 没被占用路径是唯一确定的。这种小样例手动推一遍比在 LeetCode 上反复提交试错快得多。推完之后再检查代码里每一步标记、恢复写的位置基本能定位 90% 的问题。我刷热题 100 时养成的习惯是凡是回溯题先推一个最小 case再写代码AC 率会明显提升。约 300 字6. 刷题中的实战体会与举一反三6.1 热题 100 里和回溯强相关的题目怎么串联刷完单词搜索我建议趁热把热题 100 里的回溯题按顺序过一遍全排列、子集、组合总和、括号生成。它们的共同模板都是backtrack(路径, 选择列表): if 满足结束条件: 记录结果 return for 选择 in 选择列表: 做选择 backtrack(路径, 选择列表) 撤销选择单词搜索的特殊之处只在于“选择列表”不是固定的数组而是当前格子的上下左右。把这一点想明白DFS 回溯题在你眼里就不再是几十道孤立题目而是一套可以套用的思维框架。我在刷这组题时会刻意用同一个模板去写每道题的代码框架只有决策和约束部分不同后面再遇到新题写起来非常快。约 300 字6.2 实际做题时我的几个习惯最后分享两个我自己常用的实操技巧。一是先写“伪代码酒精测试”。真正动键盘前用伪代码把 dfs 的参数、返回条件、标记、恢复四步写全对着 word 的例子手动走一遍。这一步能挡掉至少一半的边界错误尤其适合新手。二是善用 LeetCode 的“相关题目”功能。做完单词搜索后把单词搜索 II、被围绕的区域、岛屿数量这些网格题放在同一天做。网格 DFS 的套路是共通的连续做三四道之后边界条件、方向数组、visited 标记这些动作会变成肌肉记忆后续再遇到类似题能省很多时间。如果你正在刷热题 100我的建议是不要追求一天刷很多道而是在每一道经典题上把“为什么这么做”想透。单词搜索这道题配合二分查找那类比如著名的吃香蕉问题交替练习一天两题、坚持一个月效果比我刚刷题时那种贪快乱刷好得多。我自己后来回看刷题记录真正留下印象、面试时能马上迁移的就是那些认真拆解过思路的中等题。