单词搜索

单词搜索这道题在问什么

在一个字母矩阵里判断能否找出给定单词 word：路径上相邻两个字母必须在网格中上下或左右相邻，且同一个格子在一条路径里最多用一次，返回能或不能。隐藏的难点全在最后半句——路径不能自己踩自己，比如单词里有两个相同字母，不能靠原地折返来凑，这条约束决定了解法的形态。

为什么单词搜索要用 DFS 回溯

这题找的是一条会拐弯的路径。站在任何一格，下一步有上下左右四种选择，选错了还得退回来换方向——「做选择、走不通、撤销重试」正是回溯的骨架。用 DFS 把每种走法探到底，天然覆盖所有可能路径。

有人会问能不能用 BFS。不合适：BFS 按层扩散，同一层混着许多条不同路径的分叉，而「这个格子在我这条路径里用没用过」是每条路径各自的状态，队列结构很难替每条路径单独记账。DFS 沿一条路径深入、回退时顺手清账，恰好和这条约束严丝合缝。

原地改井号当访问标记为什么成立

防重复踩的通常做法是开一个 visited 矩阵，但这题有更省的写法：进入格子时把它的字母暂存到临时变量，再把格子改成井号；递归返回前改回原字母。井号不是小写字母，绝不会等于 word 里的任何字符，所以后续匹配撞上它必然失败——效果与 visited 标记完全等价，还省掉一整个矩阵的空间。

这套标记维护着一条不变量：任何时刻被改成井号的格子，恰好就是当前这条路径踩过的格子。回溯时还原字母，意味着这个格子对其他起点、其他方向的路径重新可用。忘了还原是最经典的错误：别的路径会误以为该格已被占用，明明存在的解会被漏判成不存在。

递归函数每一步为什么是对的

递归函数 dfs(i, j, idx) 回答一个明确的问题：从格子 (i, j) 出发，能否匹配 word 从第 idx 个字符起的剩余部分。先比对当前格子与 word[idx]，不等直接失败；相等且 idx 已是最后一个字符，整个单词拼完，成功。否则标记当前格，向四个没越界、没被标记的邻格递归匹配下一个字符，任何一个方向成功即整体成功。

正确性来自问题的自我分解：单词能从 (i, j) 拼出，当且仅当首字符对上、且剩余部分能从某个邻格拼出——递归定义与题意逐字对应。外层则要把每个等于首字母的格子都试作起点，因为正确路径可能从矩阵里任何一个首字母格开始，只试一个会漏。

复杂度怎么估，哪些边界会翻车

时间 O(R·C·4^L)：R·C 个起点，每层递归最多岔出 4 个方向、最深 L 层，这是最坏上界，实际因字符不匹配会大量提前剪断。空间 O(L)：递归栈最深等于单词长度，标记原地进行不占额外矩阵。

三个真会翻车的点：一是走过的格不标记，会原地打转拼出假单词；二是回溯时忘记还原标记，会漏掉真正的解；三是递归前不判下标越界就去访问格子，会数组越界报错。