LeetCode 79：单词搜索（Word Search）题解

Word Search 是 LeetCode Hot 100 里面一道非常经典的回溯题。

这道题和前面的“子集”“全排列”“括号生成”一样，也属于深度优先搜索 / 回溯专题里的高频题。但它和那些“在数组里选数字”的回溯题又不太一样，因为这次搜索空间不再是一维数组，而是一个二维网格。

题目要求我们判断：给定一个字符网格 board 和一个字符串 word，是否能在网格中找到一条路径，使得沿着路径走过的字符刚好拼成这个单词。

注意这里有两个关键限制：

每次只能向上、下、左、右四个方向移动
同一个格子不能被重复使用

这就说明，这道题本质上是在一个二维平面上做路径搜索。你给出的这份 Java 代码，使用的是这道题最经典、最标准的一种写法：

DFS + 回溯 + 访问标记

这种写法的核心思路非常清晰：

从网格中的每个位置尝试作为起点
如果当前字符能匹配上 word[index]，就继续往四个方向搜索下一个字符
搜索过程中用 visited 记录已经走过的格子
如果某条路径走不通，就回溯撤销标记

本文就结合这段代码，系统地讲一下这道题的思路。

题目介绍

给定一个 m x n 的字符网格 board 和一个字符串 word。请你判断 word 是否存在于该网格中。

构成单词的规则是：

单词必须按照字符顺序逐个匹配
匹配时，每次只能从当前格子移动到相邻格子
相邻只包括上、下、左、右四个方向
同一个格子在一次搜索路径中不能重复使用

例如：

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED"

答案是：

true

因为可以沿着一条合法路径找到这个单词。

示例

示例 1

输入：
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCCED"

输出：true

因为存在这样一条路径：

A -> B -> C -> C -> E -> D

示例 2

输入：
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "SEE"

输出：true

因为存在路径：

S -> E -> E

示例 3

输入：
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
word = "ABCB"

输出：false

虽然前面几个字符能匹配，但由于同一个格子不能重复使用，最终无法构成 "ABCB"。

最直接的想法是什么？

如果最开始只从直觉出发，很容易想到：

看看网格里有没有 word 的第一个字符
如果有，就从那里出发，尝试往四周找第二个字符
再继续找第三个、第四个……
只要有一条路径能把整个单词拼出来，就返回 true

这个思路本身就是正确的。问题在于，当你真的开始写代码时，会马上遇到几个关键问题：

搜索该怎么展开？
同一个格子怎么避免重复使用？
如果一条路径走不通，怎么退回来继续试别的方向？

这些问题合在一起，其实就是一个非常典型的回溯模型。

核心思路：DFS + 回溯

这道题最自然的做法，就是深度优先搜索。

我们可以定义一个递归函数：

dfs(board, word, index, x, y, visited)

表示：

当前正在匹配 word[index]，并且希望从坐标 (x, y) 开始继续搜索。

如果当前格子字符和 word[index] 不相等，那这条路立刻失败。如果当前已经匹配到了单词最后一个字符，而且字符也对上了，那说明搜索成功。

否则，就把当前格子标记为已访问，然后尝试往四个方向走，继续去匹配下一个字符：

word[index + 1]

如果四个方向里有任意一个方向能成功，那整条路径就成功。如果都不行，就把当前格子的访问标记撤销，回退到上一步。

这就是回溯。

Java 代码

下面是你给出的代码，我这里保留原始逻辑，并加上注释：

class Solution {
    private int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};
    private int m, n;

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

        boolean[][] 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, visited)) return true;
            }
        }

        return false;
    }

    private boolean dfs(char[][] board, String word, int index, int x, int y, boolean[][] visited) {
        // 当前字符不匹配，直接失败
        if (board[x][y] != word.charAt(index)) return false;

        // 如果已经匹配到最后一个字符，说明成功找到
        if (index == word.length() - 1) return true;

        // 标记当前格子已访问
        visited[x][y] = true;

        boolean result = false;

        // 向四个方向继续搜索
        for (int[] direction : directions) {
            int newX = x + direction[0], newY = y + direction[1];

            if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {
                if (dfs(board, word, index + 1, newX, newY, visited)) {
                    result = true;
                    break;
                }
            }
        }

        // 回溯：撤销访问标记
        visited[x][y] = false;

        return result;
    }
}

代码拆解

这段代码就是标准的二维网格回溯模板。下面一步一步来看。

1. 为什么要定义 `directions`？

private int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};

因为题目规定每次只能朝四个方向移动：

上：(-1, 0)
下：(1, 0)
左：(0, -1)
右：(0, 1)

把这四个方向统一存进数组后，后面搜索时就可以直接用循环来遍历四个方向，而不用重复写四段代码。

这也是网格 DFS / BFS 题里非常常见的一种写法。

2. 为什么要记录 `m` 和 `n`？

private int m, n;

因为在 DFS 的过程中，我们会频繁判断坐标是否越界：

newX >= 0 && newX < m && newY >= 0 && newY < n

所以提前把行数和列数保存下来，后面递归里使用会更方便。

3. 为什么要从每个位置都尝试作为起点？

for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
        if (dfs(board, word, 0, i, j, visited)) return true;
    }
}

因为题目并没有告诉我们单词一定从哪个格子开始。所以只能枚举整个网格中的每一个位置，把它当作潜在起点去尝试。

只要其中有一个位置能成功匹配整条单词路径，就可以直接返回 true。

如果所有位置都试过了还是不行，那答案就是 false。

这一步其实很像“多源起点搜索”。

4. `dfs` 里的 `index` 表示什么？

private boolean dfs(char[][] board, String word, int index, int x, int y, boolean[][] visited)

index 表示：

当前正在匹配 word 的第几个字符。

也就是说：

如果 index = 0，说明当前要匹配单词第一个字符
如果 index = 1，说明当前要匹配第二个字符
…
如果 index == word.length() - 1，说明当前正在匹配最后一个字符

这个参数非常关键，因为它把“当前走到单词的哪一步”这个状态带进了 DFS 中。

5. 为什么字符不匹配就直接返回 `false`？

if (board[x][y] != word.charAt(index)) return false;

因为这道题要求路径上的字符必须严格按顺序匹配。

如果当前位置字符都对不上当前目标字符，那就说明这条路径不可能成功，没必要继续往下搜。

这一步相当于一个很强的剪枝。

6. 为什么当 `index == word.length() - 1` 时返回 `true`？

if (index == word.length() - 1) return true;

因为这表示：

当前格子字符已经和单词最后一个字符匹配成功
而且前面的递归过程已经保证前缀也都匹配成功

所以整条单词路径已经完整找到，可以直接返回 true。

这就是递归的终止条件。

7. 为什么要用 `visited` 数组？

boolean[][] visited = new boolean[m][n];

因为题目明确规定：

同一个格子不能在同一条搜索路径中重复使用。

所以当我们走到某个格子时，必须把它标记为已访问。后面继续搜索相邻格子时，如果某个格子已经访问过，就不能再走进去。

这正是 visited 的作用。

例如：

在 "ABCB" 这个例子里，虽然字符分布上看似可能拼出来
但因为有一步需要重复用同一个 B 所在格子
所以实际上是不合法的

8. 为什么搜索前要先标记，搜索后要撤销？

visited[x][y] = true;
...
visited[x][y] = false;

这是回溯的标准操作。

标记当前格子

表示当前路径已经走到了这里，这个格子本轮不能再重复使用。

搜索结束后撤销标记

因为如果当前路径走不通，我们要退回来，尝试别的方向。一旦退回来，这个格子在新的搜索分支里又应该重新变成“可用”。

所以这两句代码本质上就是：

进入递归前，做选择
离开递归前，撤销选择

这正是回溯的核心。

9. 为什么要遍历四个方向？

for (int[] direction : directions) {
    int newX = x + direction[0], newY = y + direction[1];
    ...
}

因为从当前格子出发，下一步只能去四个相邻方向中的某一个。

所以我们需要枚举：

只要四个方向中有任意一个方向能继续把后面的字符匹配成功，那么整条路径就成立。

10. 为什么还要判断边界和访问状态？

if (newX >= 0 && newX < m && newY >= 0 && newY < n && !visited[newX][newY]) {

因为下一步搜索必须满足两个条件：

条件 1：不能越界

二维网格搜索时，最基础的检查就是坐标是否仍然在合法范围内。

条件 2：不能走到已经访问过的格子

否则会违反题目的“不重复使用”规则。

这两个判断是网格 DFS 题里的标准模板。

手动模拟一遍

我们用最经典的样例来走一下：

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

word = "ABCCED"

第一步：枚举起点

从 (0,0) 开始：

board[0][0] = 'A'

刚好等于 word[0] = 'A'，于是开始 DFS。

第二步：匹配 `B`

从 (0,0) 出发，往四周找 word[1] = 'B'。

右边 (0,1) 是 'B'，匹配成功，继续往下搜。

第三步：匹配 `C`

从 (0,1) 往四周找 word[2] = 'C'。

右边 (0,2) 是 'C'，继续。

第四步：匹配第二个 `C`

从 (0,2) 往四周找 word[3] = 'C'。

下边 (1,2) 是 'C'，继续。

第五步：匹配 `E`

从 (1,2) 往四周找 word[4] = 'E'。

下边 (2,2) 是 'E'，继续。

第六步：匹配 `D`

从 (2,2) 往四周找 word[5] = 'D'。

左边 (2,1) 是 'D'，匹配成功，而且这已经是单词最后一个字符。

所以整条路径成功，函数返回 true。

为什么这个方法是正确的？

因为题目要求的是：

按顺序匹配单词
每一步只能去相邻格子
同一格子不能重复使用

而 DFS + 回溯正好完整地模拟了这个过程：

DFS

负责从当前格子出发，递归地尝试匹配下一个字符。

`visited`

负责保证同一路径中不会重复使用同一个格子。

回溯

负责在某条路径失败时，恢复现场，继续尝试其他可能路径。

这样一来：

所有可能的合法路径都会被尝试到
非法路径会被及时剪枝
只要存在一条成功路径，就一定能找到

因此这个算法是正确的。

复杂度分析

假设：

网格大小为 m x n
单词长度为 L

时间复杂度

最坏情况下，我们会从每个格子出发尝试搜索：

m * n

次。

而每次 DFS 最坏可能向四个方向分支扩展。粗略估计，复杂度常写为：

O(m * n * 4^L)

更精确一点，由于第一步之后每层通常最多走 3 个未访问方向，也常写成：

O(m * n * 3^L)

但博客里一般写前者更直观也更常见。

空间复杂度

主要来自：

visited 数组：O(m * n)
递归调用栈：最深 O(L)

所以整体辅助空间复杂度可以写为：

O(m * n + L)

这道题真正想考什么？

这道题表面上是在找单词，但本质上考察的是二维回溯搜索的基本功。

第一，是否能把一维回溯迁移到二维网格

前面很多回溯题都在数组或字符串上做选择。这题则要求你把回溯思维迁移到二维平面中。

第二，是否能正确处理“访问标记”

只要题目中有：

走过的格子不能重复使用
一条路径中不能重复访问节点

就应该立刻想到 visited。

第三，是否能写好回溯恢复现场

如果不把 visited[x][y] 恢复成 false，后面的分支搜索就会被错误影响。

所以这道题很适合训练回溯的细节处理。

和“岛屿数量”有什么区别？

这两题都在二维网格里做 DFS，但本质目标不同。

单词搜索

是路径型搜索：

有严格顺序
要按字符依次匹配
同一路径中不能重复用格子

岛屿数量

是连通块搜索：

只关心区域连通性
不关心路径顺序
访问过的格子通常直接标记掉，不再恢复

所以这题更像是“网格中的路径回溯”，而不是普通的网格遍历。

总结

这道题的核心思想可以概括成一句话：

从网格中的每个位置出发，用 DFS 按顺序匹配单词字符，并通过 visited 和回溯机制保证同一条路径中格子不重复使用。

具体步骤就是：

枚举网格中的每个格子作为起点
如果当前字符和 word[index] 不匹配，直接返回失败
如果已经匹配到最后一个字符，返回成功
否则标记当前格子已访问
向上、下、左、右四个方向继续搜索下一个字符
如果四个方向都失败，则撤销访问标记并回溯

这样就能正确判断单词是否存在。

这是一道非常经典、也非常值得反复理解的回溯题。因为它会让你真正体会到：

二维网格中的 DFS 怎么写
回溯在路径搜索题里为什么重要
visited 和恢复现场到底在保护什么

把这道题真正吃透之后，再去看：

岛屿数量
被围绕的区域
单词搜索 II
N 皇后

这些 DFS / 回溯题时，你会更容易看出它们的共同框架。

因为“单词搜索”本身就是二维回溯题里非常经典的一道模板题。