LeetCode 79. 单词搜索
目录
题目描述
✅ 79. 单词搜索
题意分析
给定一个 $m \times n$ 的字符网格和一个单词，问能否从网格中某个格子出发，每一步走到上、下、左、右相邻的格子，依次拼出整个单词。拼的过程中有一条硬约束：同一条路径里，同一个格子不能重复使用——比如单词是
"ABAB"，不能在两个格子之间来回横跳。注意几个容易忽略的题意细节：起点可以是网格中的任意格子，不限于左上角；只能走四邻方向，对角线不算相邻；只需要判断存在性，不需要输出路径。
数据范围是明显的信号：网格最大 $6 \times 6$，单词最长 15。这么小的规模意味着题目允许指数级的尝试，同时提示我们「不能重复用格子」这个约束需要一种随路径动态变化的记录方式——某个格子是否可用，取决于当前这条路径走没走过它，而不是全局走没走过。
解法：回溯搜索相邻字符路径
核心思路
问题关键：起点不固定，下一步有四个方向，而且“格子不能重复使用”只约束当前路径。选择一旦依赖前面的路径，就需要尝试、撤销，这正是回溯模型。
为什么选 DFS 回溯：从每个可能的起点出发，边走边匹配
word[idx]；字符不等时立即剪枝，不必生成完整路径。进入格子后临时写成'#'，离开时恢复，可用 $O(1)$ 额外标记代替visited数组。不变量与正确性：调用
dfs(row, col, idx)时，word[0..idx-1]已由一条不重复路径匹配完成，路径上的格子均被标记。当前字符匹配后，只需考察四个相邻格子能否完成剩余后缀；四个方向覆盖所有合法下一步。函数返回前恢复现场，因此不同分支互不影响。
解题步骤
- 若单词长度超过格子总数，直接返回
false。- 枚举每个格子作为起点，调用
dfs(row, col, 0)；任一起点成功即可结束。- DFS 先检查边界，再检查当前格子是否等于
word[idx]；不满足立即返回。- 当前字符是最后一个字符时返回
true，否则标记当前格子，递归搜索上下左右并匹配idx + 1。- 无论搜索成功还是失败，都先恢复当前格子，再把结果返回上一层。
代码实现
class Solution {
public boolean exist(char[][] board, String word) {
if (word.length() > board.length * board[0].length) {
return false;
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (dfs(board, word, i, j, 0)) {
return true;
}
}
}
return false;
}
private boolean dfs(char[][] board, String word, int row, int col, int idx) {
if (row < 0 || row == board.length || col < 0 || col == board[0].length) {
return false;
}
if (board[row][col] != word.charAt(idx)) {
return false;
}
if (idx == word.length() - 1) {
return true;
}
char origin = board[row][col];
board[row][col] = '#';
boolean found = dfs(board, word, row - 1, col, idx + 1)
|| dfs(board, word, row + 1, col, idx + 1)
|| dfs(board, word, row, col - 1, idx + 1)
|| dfs(board, word, row, col + 1, idx + 1);
board[row][col] = origin;
return found;
}
}
func exist(board [][]byte, word string) bool {
if len(word) > len(board)*len(board[0]) {
return false
}
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
if dfsWord(board, word, i, j, 0) {
return true
}
}
}
return false
}
func dfsWord(board [][]byte, word string, row int, col int, idx int) bool {
if row < 0 || row == len(board) || col < 0 || col == len(board[0]) {
return false
}
if board[row][col] != word[idx] {
return false
}
if idx == len(word)-1 {
return true
}
origin := board[row][col]
board[row][col] = '#'
found := dfsWord(board, word, row-1, col, idx+1) ||
dfsWord(board, word, row+1, col, idx+1) ||
dfsWord(board, word, row, col-1, idx+1) ||
dfsWord(board, word, row, col+1, idx+1)
board[row][col] = origin
return found
}
复杂度分析
- 时间复杂度：$O(mn \cdot 3^L)$，其中 $L$ 是单词长度。起点有 $mn$ 个；第一步后，来路已被标记，每层最多继续向 3 个方向搜索。
- 空间复杂度：$O(L)$，原地标记不需要访问数组，额外空间来自最深为 $L$ 的递归栈。
关键点总结
- 递归状态只保留位置和待匹配下标，已经匹配的前缀由调用栈表达。
- 判断顺序是“越界 → 字符不等 → 已匹配完成”，避免越界和提前成功。
- 原地标记必须与恢复成对出现；它只屏蔽当前路径，不能污染其他起点。
- 面试复杂度可进一步解释为：第一层最多 4 个方向，后续最多 3 个，渐进上界写作 $O(mn \cdot 3^L)$。
易错点总结
- 先读
board[row][col]再判边界：从边缘向外搜索时会数组越界。- 在比较当前字符前判断
idx到末尾：board = [["A"]]、word = "B"会被误判为成功。- 找到一个方向后直接返回、没有恢复现场：结果虽可能正确，但输入网格被改坏；应先保存结果、恢复，再返回。
- 失败后不撤销访问标记：前一个起点会污染后一个起点，导致漏解。
- 搜索对角线：
[["A","B"],["C","D"]]中的"AD"不合法，只允许上下左右。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 212. 单词搜索 II | 困难 | 多单词同时搜索，需用字典树合并前缀剪枝 |
| 980. 不同路径 III | 困难 | 回溯计数而非判存在，要求恰好走遍所有空格 |
| 1219. 黄金矿工 | 中等 | 路径不受目标串约束，回溯中求最大收益 |
| 200. 岛屿数量 | 中等 | 全局访问一次的洪泛填充，标记不需要撤销 |
| 剑指 Offer 12. 矩阵中的路径 | 中等 | 与本题同一模型，可用于检验模板熟练度 |