本文概览：本文以LeetCode题目"单词搜索"为例，讲解为什么用DFS不用BFS，以及DFS在二维网格中的编写套路

一、题目

单词搜索题目

二、题目分析

这题要求在二维网格中找单词，有三个要求：

  1. 必须从单词的第一个字符开始
  2. 字符必须上下左右相邻（不能跳格子）
  3. 同一个位置的字符不能重复使用

比如要找 "ABC"，网格是：

1
2
A C B
D E F

这不算，因为 A 的上下左右没有 B（A 的右边是 C，下边是 D），所以无法组成连续的 "AB"。

什么是"连续"？ 就是每一步只能走到上下左右相邻的格子，不能跳着走。

思路概览

Java 实现代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    private int m, n;
    private boolean[][] visited;
    private final int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public boolean exist(char[][] board, String word) {
        m = board.length;
        n = board[0].length;
        visited = new boolean[m][n];

        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;
    }

    private boolean dfs(char[][] board, String word, int index, int i, int j) {
        // 1. 所有字符匹配完毕，直接成功（优先于越界判断）
        if (index == word.length()) {
            return true;
        }
        // 2. 越界检查
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return false;
        }
        // 3. 已访问或字符不匹配
        if (visited[i][j] || board[i][j] != word.charAt(index)) {
            return false;
        }

        // 4. 标记当前格子
        visited[i][j] = true;

        // 5. 向四个方向递归
        for (int[] dir : dirs) {
            if (dfs(board, word, index + 1, i + dir[0], j + dir[1])) {
                visited[i][j] = false;
                return true;
            }
        }

        // 6. 回溯
        visited[i][j] = false;
        return false;
    }
}

思路简要说明：

  1. 外层双重循环遍历每个格子作为起点，调用 DFS 尝试匹配
  2. DFS 内部先判断出口（匹配完成、越界、字符不匹配），再标记当前格子，向四方向递归，最后回溯
  3. 用一个 visited 数组记录已访问的格子，回溯时恢复为 false

三、思路详解

第一步：为什么用 DFS 不用 BFS

这题和前面的岛屿数量很像，都是二维网格 + 四方向递归。岛屿数量用 DFS 或 BFS 都行，但这题强烈推荐 DFS，不推荐 BFS。

为什么？因为 BFS 需要记录每条路径的访问状态。

举个例子，假设从 A 出发，走到 B 后有两条路：

1
2
路径1：A → B → C → ...
路径2：A → B → D → ...

如果用 BFS，队列里会同时存在这两条路径。路径1 访问了 C，路径2 访问了 D，它们的 visited 状态是不同的——路径1 不能再用 C，路径2 不能再用 D，但两条路径都不能用 A 和 B。

如果用一个全局 visited，路径1 标记了 C，路径2 就看不到 C 了，但路径2 可能本来是可以走 C 的（只是路径1 先走了）。

所以 BFS 要么给每个队列元素配一个独立的 visited 副本（空间开销大），要么用更复杂的状态记录方式（代码复杂）。

而 DFS 就简单多了：一个全局 visited 数组，走到哪标记到哪，走不通就回溯恢复。同一时刻只有一条路径在走，visited 状态天然就是当前路径的访问记录。

第二步：DFS 编写套路（和岛屿数量对比）

这题的 DFS 框架和岛屿数量几乎一样：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 岛屿数量的 DFS
private void dfs(char[][] grid, int i, int j) {
    if (越界 || grid[i][j] == '0') return;
    grid[i][j] = '0';  // 标记
    for (int[] dir : dirs) {
        dfs(grid, i + dir[0], j + dir[1]);
    }
}

// 单词搜索的 DFS
private boolean dfs(char[][] board, String word, int index, int i, int j) {
    if (index == word.length()) return true;  // 匹配完成
    if (越界 || visited[i][j] || board[i][j] != word.charAt(index)) return false;
    visited[i][j] = true;  // 标记
    for (int[] dir : dirs) {
        if (dfs(board, word, index + 1, i + dir[0], j + dir[1])) return true;
    }
    visited[i][j] = false;  // 回溯
    return false;
}

区别在于：

岛屿数量 单词搜索
目标 标记整个岛屿 找到一条匹配路径
标记方式 直接改 grid[i][j] = '0' 用 visited 数组
回溯 不需要（标记完就不管了） 需要（走不通要恢复）
返回值 void boolean

第三步：递归出口的三个判断

DFS 函数开头有三个判断，顺序很重要：

1
2
3
4
5
6
7
8
9
10
11
12
// 1. 所有字符匹配完毕，直接成功
if (index == word.length()) {
    return true;
}
// 2. 越界检查
if (i < 0 || i >= m || j < 0 || j >= n) {
    return false;
}
// 3. 已访问或字符不匹配
if (visited[i][j] || board[i][j] != word.charAt(index)) {
    return false;
}

为什么 index == word.length() 要放在最前面？

因为当 index 到达 word.length() 时，说明所有字符都匹配完了，此时 i, j 可能是越界的（最后一个字符的下一个位置）。如果先判断越界，就会错误地返回 false。

举个例子，单词 "AB"，网格是：

1
A B

匹配流程：

  • dfs(0, 0)：board[0][0] = 'A'，匹配，标记，递归 dfs(0, 1)
  • dfs(0, 1)：board[0][1] = 'B'，匹配，标记，递归 dfs(0, 2)
  • dfs(0, 2)：index = 2 = word.length()，返回 true

如果先判断越界，dfs(0, 2) 会因为 j >= n 返回 false，就错了。

第四步：标记 + 四方向递归 + 回溯

匹配成功后，标记当前格子，向四方向递归：

1
2
3
4
5
6
7
8
9
10
11
visited[i][j] = true;  // 标记

for (int[] dir : dirs) {
    if (dfs(board, word, index + 1, i + dir[0], j + dir[1])) {
        visited[i][j] = false;  // 找到即返回，也恢复一下
        return true;
    }
}

visited[i][j] = false;  // 回溯
return false;

为什么要回溯？

因为当前路径走不通，要退回去尝试其他路径。如果不恢复 visited[i][j] = false，其他路径就看不到这个格子了。

举个例子，从 A 出发，先往右走 B，再往右走 C，发现 C 的下一个字符不匹配，回溯。此时 A 还要尝试往下走，如果 B 没有被恢复，A 往下走的路径就看不到 B 了（虽然这条路径本来也不经过 B，但 visited 状态是全局的）。

第五步：完整执行过程

以示例为例：

1
2
3
4
5
6
board = [
  ['A', 'B', 'C', 'E'],
  ['S', 'F', 'C', 'S'],
  ['A', 'D', 'E', 'E']
]
word = "ABCCED"

外层循环从 (0, 0) 开始，board[0][0] = 'A'，匹配 word[0]，开始 DFS。

最终找到的路径在网格上长这样：

1
2
3
4
5
6
7
8
9
10
    0   1   2   3
  ┌───┬───┬───┬───┐
0 │ A→│ B→│ C │ E │
  ├───┼───┼───┼───┤
  │   │   │ ↓ │   │
1 │ S │ F │ C │ S │
  ├───┼───┼───┼───┤
  │   │ ← │   │   │
2 │ A │ D │ E │ E │
  └───┴───┴───┴───┘

路径：(0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,1)，对应字符 "ABCCED"。

下面用表格展示每一步的状态变化：

步骤 当前位置 字符 匹配 word 的哪个字符 下一步尝试 结果
1 (0,0) A word[0] 向右到 (0,1) 继续
2 (0,1) B word[1] 向右到 (0,2) 继续
3 (0,2) C word[2] 向右到 (0,3) E≠C，失败，回溯
4 (0,2) C word[2] 向下到 (1,2) 继续
5 (1,2) C word[3] 向右到 (1,3) S≠E，失败，回溯
6 (1,2) C word[3] 向下到 (2,2) 继续
7 (2,2) E word[4] 向右到 (2,3) E≠D，失败，回溯
8 (2,2) E word[4] 向左到 (2,1) 继续
9 (2,1) D word[5] index=6=word.length() 成功！

注意第 3 步和第 4 步：在 (0,2) 这个位置，先尝试向右走，发现不匹配，回溯后再尝试向下走。这就是 DFS 的回溯机制——一条路走不通就退回来换一条路。

第六步：DFS vs BFS 对比

DFS BFS
数据结构 递归栈 队列
visited 一个全局数组 每个路径需要独立副本
回溯 天然支持（递归返回时恢复） 需要额外处理
空间复杂度 O(mn + L)，L 是单词长度 O(mn × 路径数)
代码复杂度 简单 复杂

这题用 DFS 是标准做法，BFS 虽然理论上可行，但实现起来麻烦且效率低。

四、总结

这题和岛屿数量一样，都是二维网格 + 四方向递归，核心区别在于：

  1. 岛屿数量不需要回溯（标记完就不管了），单词搜索需要回溯（走不通要恢复）
  2. 岛屿数量用 DFS 或 BFS 都行，单词搜索强烈推荐 DFS（BFS 的 visited 管理太复杂）

DFS 的编写套路：

  1. 判断出口（匹配完成、越界、字符不匹配）
  2. 标记当前格子
  3. 四方向递归
  4. 回溯恢复

这个套路适用于所有"在网格中找路径"的题目。