单词搜索 图解题解

单词搜索这道题在问什么

在一个字母矩阵里判断能否找出给定单词 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)：递归栈最深等于单词长度，标记原地进行不占额外矩阵。

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

Python

def exist(board, word):
    R, C = len(board), len(board[0])
    def dfs(i, j, idx):
        if board[i][j] != word[idx]: return False
        if idx == len(word) - 1: return True
        tmp = board[i][j]
        board[i][j] = "#"            # 标记已用
        for di, dj in ((-1,0),(0,1),(1,0),(0,-1)):
            ni, nj = i + di, j + dj
            if 0 <= ni < R and 0 <= nj < C \
               and board[ni][nj] != "#" \
               and dfs(ni, nj, idx + 1):
                board[i][j] = tmp; return True
        board[i][j] = tmp            # 回溯撤销
        return False
    for i in range(R):
        for j in range(C):
            if dfs(i, j, 0): return True
    return False

C++

class Solution {
    int R, C;
    bool dfs(vector<vector<char>>& b, string& w,
             int i, int j, int idx) {
        if (b[i][j] != w[idx]) return false;
        if (idx == (int)w.size() - 1) return true;
        char tmp = b[i][j];
        b[i][j] = '#';              // 标记已用
        int d[5] = {-1, 0, 1, 0, -1};
        for (int k = 0; k < 4; k++) {
            int ni = i + d[k], nj = j + d[k + 1];
            if (ni >= 0 && ni < R && nj >= 0 && nj < C
                && b[ni][nj] != '#'
                && dfs(b, w, ni, nj, idx + 1)) {
                b[i][j] = tmp; return true;
            }
        }
        b[i][j] = tmp;              // 回溯撤销
        return false;
    }
public:
    bool exist(vector<vector<char>>& b, string w) {
        R = b.size(); C = b[0].size();
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (dfs(b, w, i, j, 0)) return true;
        return false;
    }
};

Java

class Solution {
    int R, C;
    int[] d = {-1, 0, 1, 0, -1};
    boolean dfs(char[][] b, String w, int i, int j, int idx) {
        if (b[i][j] != w.charAt(idx)) return false;
        if (idx == w.length() - 1) return true;
        char tmp = b[i][j];
        b[i][j] = '#';            // 标记已用
        for (int k = 0; k < 4; k++) {
            int ni = i + d[k], nj = j + d[k + 1];
            if (ni >= 0 && ni < R && nj >= 0 && nj < C
                && b[ni][nj] != '#'
                && dfs(b, w, ni, nj, idx + 1)) {
                b[i][j] = tmp;
                return true;
            }
        }
        b[i][j] = tmp;            // 回溯撤销
        return false;
    }
    public boolean exist(char[][] b, String w) {
        R = b.length; C = b[0].length;
        for (int i = 0; i < R; i++)
            for (int j = 0; j < C; j++)
                if (dfs(b, w, i, j, 0)) return true;
        return false;
    }
}