单词搜索如何用回溯（DFS）求解？（LeetCode 79）

简化版

在字符网格里判断某个单词能否由相邻（上下左右）格子依次连成，且同一格不能重复用。做法是从每个格子当起点做 DFS：当前格字符匹配单词第 k 位就往四个方向递归找第 k+1 位。回溯的关键是进入某格时把它标记为已访问、四个方向都试完后再恢复——这样同一条路径里不重复用格子，不同路径又能复用。复杂度约 O(m·n·4^L)（L 为单词长度）。

详细版

boolean exist(char[][] board, String word) {
    int m = board.length, n = board[0].length;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (dfs(board, word, 0, i, j)) return true; // 每个格子当起点
    return false;
}
boolean dfs(char[][] b, String w, int k, int i, int j) {
    // 越界 或 当前格不等于单词第 k 个字符 → 此路不通
    if (i < 0 || i >= b.length || j < 0 || j >= b[0].length || b[i][j] != w.charAt(k))
        return false;
    if (k == w.length() - 1) return true;         // 最后一个字符也匹配上了
    char tmp = b[i][j];
    b[i][j] = '#';                                 // 标记已访问（就地）
    boolean found = dfs(b, w, k + 1, i + 1, j)     // 下
                 || dfs(b, w, k + 1, i - 1, j)     // 上
                 || dfs(b, w, k + 1, i, j + 1)     // 右
                 || dfs(b, w, k + 1, i, j - 1);    // 左
    b[i][j] = tmp;                                 // 回溯：恢复原字符
    return found;
}

起点枚举：单词可能从任意格开始，所以双重循环对每个格子发起 DFS。
回溯的标记与恢复：进入格子设 '#'（本条路径内不可再用），四方向试完恢复成原字符（让别的路径还能用它）。
短路 ||：任一方向找到就立即返回 true，不再试其余方向。
复杂度 O(m·n·4^L)：每格起点，每步至多 4 个方向、深度 L。

完整版教学

一、问题：网格中找相邻路径

单词搜索：给一个字符矩阵和一个单词，判断单词能否在网格中连续相邻地拼出来。相邻指上下左右四方向，路径不能拐到自己走过的格子（同一格在一次拼写中只用一次）。例如网格里 ABCCED 能沿相邻格连成就返回 true。

这本质是在网格（隐式图）上做 DFS 搜索路径，并在走不通时回溯，是「回溯 + 图遍历」的典型。

二、从每个格子起试：四方向 DFS

单词的第一个字符可能出现在网格任何位置，所以外层双重循环把每个格子都当作起点发起一次 DFS。DFS 的参数 k 表示「当前要匹配单词的第几个字符」，(i,j) 是当前格子：

先判边界和字符：越界、或 board[i][j] != word[k]，此路不通返回 false；
若 k 已是单词最后一位且匹配，说明整词拼成，返回 true；
否则朝四个方向递归找第 k+1 位，任一方向成功即成功。

三、回溯核心：标记访问 + 撤销恢复

难点在「同一格不能重复使用」。如果不管，DFS 可能在 A→B→A→B 之间来回横跳。解决办法是回溯式的「占用—释放」：

进入 (i,j) 时，把它临时改成一个不会匹配任何字符的标记（如 '#'）——这样在从它出发的更深递归里，就算绕回这一格，board[i][j] != word[k] 判断会失败，天然阻止重复使用；
四个方向都递归完后，把 board[i][j] 恢复成原字符 tmp。

恢复这一步就是回溯的灵魂：它让这个格子只在「当前这条正在尝试的路径」里被独占，一旦回退，格子重新可用，供其它路径使用。 忘了恢复，会错误地把格子永久占用，导致本可拼成的单词判成 false。

四、就地标记 vs visited 数组

标记访问有两种等价写法：

就地改字符（本题用）：把 board[i][j] 暂存后改成 '#'，回溯时还原。省一个数组、不额外占空间，但会临时修改输入（面试中若要求不改输入，就别用这种）。
额外 boolean[][] visited：进入置 true、回溯置 false，不改动原网格，逻辑更清晰，代价是 O(m·n) 额外空间。

两者思路完全一样，都是「进入占用、退出释放」。就地标记更省内存，visited 更安全，视要求选用。

五、复杂度分析

起点：m×n 个格子各发起一次 DFS。
每次 DFS：第一步四个方向，之后每步因为「来的方向已被标记占用」实际至多 3 个新方向，深度为单词长度 L。粗略上界 O(4^L)。
合计约 O(m·n·4^L)，空间 O(L)（递归栈；若用 visited 再加 O(m·n)）。

指数来自搜索的分支，实际有大量剪枝（字符不匹配立即返回），远达不到上界。

六、把状态、选择与撤销画成决策树

本题递归状态的精确定义是：递归状态 (r,c,index) 表示当前格匹配 word[index]，同一路径中的格子不可重复使用。状态含义越清楚，结束条件、候选范围和去重位置越容易从题意推出。

进入节点：检查当前状态与剩余目标
枚举候选：先判断约束和剪枝条件
做选择：同步修改 path / used / 约束集合
递归下一层
撤销选择：恢复到进入本节点前的状态

带数字推演：3×4 棋盘搜索 ABCCED 会依次匹配相邻 6 格；若不标记，可能在 A↔B 之间来回复用。画树时只需展开能体现“同层选择”和“纵向递归”区别的两三层，并标出被剪掉的分支，便能解释去重或剪枝为什么不会漏解。

记忆钩子：回溯不是“递归试一试”，而是维护状态不变量；做选择与撤销必须镜像，剪枝必须证明被删分支不可能产生答案。

七、复杂度、剪枝代价与实现边界

关键实现边界是：先统计棋盘字符频次可提前拒绝；可从更稀有的单词端开始；递归深度等于单词长度。回溯复杂度不能只写一个固定模板，应说明树深、每层分支数、合法叶子数以及复制答案的成本。

维度	自检问题
状态	参数能否唯一描述当前节点
候选	是否遗漏合法选择或重复枚举
剪枝	条件是必要条件还是拍脑袋
撤销	path、标记和计数是否全部恢复
输出	保存的是快照还是共享可变引用

测试应包含无解、唯一解、多解、最小规模、全部候选相同或冲突密集的输入。对可变字符串、棋盘和标记数组，还应在递归返回后断言状态与进入前一致；这类断言比只比较最终答案更容易定位撤销错误。

八、常见误区与追问

误区：全局 visited 一旦标记就不恢复。 它只约束当前路径，兄弟起点仍可使用该格。
误区：可以斜向移动。 经典题只允许上下左右，除非题目另说。
误区：复杂度是 O(mn·4^L)。 第一步后通常不能立刻回头，可更紧估 O(mn·3^(L-1))，但四次幂是安全上界。
追问：何时返回成功？ index 到达单词长度，说明此前字符都已匹配。
追问：就地标记有什么代价？ 节省 visited 空间但会短暂修改输入，必须可靠恢复。
追问：怎样做预剪枝？ 比较字符频次、长度，并从出现更少的首尾字符方向搜索。

九、加强记忆

单词搜索 = 网格上的回溯 DFS：每个格子当起点，字符匹配就朝上下左右递归找下一个字符。回溯灵魂是进入格子标记已访问（就地改 '#' 或用 visited）、四方向试完再恢复——让格子只在当前路径内独占，回退后释放。用短路 ||：任一方向成功立即返回。复杂度约 O(m·n·4^L)。就地标记省空间但改输入，visited 数组不改输入更安全。

简化版

详细版