LeetCode 79中等网格回溯
单词搜索 图解题解
这道题到底在问什么
判断
word 能否在网格里相邻连续拼出：每一步只能走上下左右，且同一格不能重复用。- board
- A B E / S F C / A D E
- word
- "ABF"
- 输出
- true
先想最直接的笨办法
最直接的想法：拿每个格子当起点暴力试。但只要不把「正在走的路径」标记成用过，就会从 A 走到 B、又从 B 退回 A，原地来回、甚至无限绕——根本停不下来。（动画第 3 步）
最优解：一步一步想明白
- 3最直接的想法：拿每个格子当起点暴力试。但只要不把「正在走的路径」标记成用过，就会从 A 走到 B、又从 B 退回 A，原地来回、甚至无限绕——根本停不下来。
- 4关键招是回溯：进入 (i,j) 先把它改成占位符
#（占住，四向递归就不会再踩它），等这一格的所有方向都探完，再把它改回原字母。这样别的起点、别的方向还能复用这格。匹配当前字符 → 占住 → 四向找下一个字符 → 撤销，是这题的主循环。 - 5匹配 word[0]='A'扫格子找单词首字母：(0,0)=A 和 word[0]='A' 对上，从这里开始 DFS，目标是接着找 word[1]='B'。
- 6word[1]='B'把 (0,0) 临时改成
#占住（灰）。看它四周找 'B'：上、左越界，下方 (1,0)=S 不是 B，右边 (0,1)=B 对上了，走过去。 - 7已匹配 'AB'，下一个 'F'把 (0,1)=B 也占住（灰）。前两个字符 'AB' 已经拼上，现在要在 B 的四个邻居里找 word[2]='F'，按「上右下左」顺序逐个试。
- 8word[2]='F'，看 (0,2)B 上方越界，先看右邻 (0,2)=E，递归进去比一比：它等于要找的 'F' 吗？
- 9(0,2)='E' ≠ 'F'负例：(0,2)=E，不等于要找的 'F'，这一格直接失败返回，不会占住它、也不会往下递归。回到 B，继续试 B 的下一个方向。
- 10(1,1)='F' 命中E 不通，换试 B 下方 (1,1)=F——正好是要找的 'F'！走过去。这一步就是「走不通就回退、换下一个方向」。
- 11"ABF" 全部拼出(1,1)=F 是 word 的最后一个字符，k 已经到末尾，整条路径 A→B→F 拼全 → 返回 true。（若这格也没拼下去，就会一路回退、把沿途 # 改回原字母，换起点重来。）
- 12# 改回原字母收尾看清「撤销」这步：递归往回退时，沿途的 (1,1)、(0,1)、(0,0) 依次把
#改回 F、B、A，网格恢复原样。这样换别的起点搜索时，这些格子还是干净可用的。 - 15凡是「在网格里搜一条满足条件的路径」都是网格回溯：进格子先占住防重复，走不通就撤销标记、退回换方向。迷宫、最长递增路径、岛屿连通都是它的变体。
- 20把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。
⚠️ 容易写错的地方
✗ 错：走进格子不标记用过
✓ 对：进入就临时占住（改成 #）
不占住会从 A 走到 B 又退回 A，原地来回、把同一格重复用，永远停不下来
✗ 错：递归后忘了把 # 改回原字母
✓ 对：四向探完后恢复原值
不撤销会污染别的起点的搜索，让本能拼出的单词被误判为找不到
✗ 错：先递归再判越界/匹配
✓ 对：先判越界与是否匹配，再决定递归
顺序反了会下标越界报错，或拿越界格去比字符
完整代码（Python / C++ / Java）
Python
class Solution:
def exist(self, board, word):
m, n = len(board), len(board[0])
def dfs(r, c, i):
if i == len(word):
return True
if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[i]:
return False
ch = board[r][c]
board[r][c] = '#'
found = dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1) or dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1)
board[r][c] = ch
return found
for r in range(m):
for c in range(n):
if dfs(r, c, 0):
return True
return FalseC++
class Solution {
public:
int m, n;
bool dfs(vector<vector<char>>& board, string& word, int r, int c, int i) {
if (i == word.size()) return true;
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word[i]) return false;
char ch = board[r][c];
board[r][c] = '#'; // 占位防重复走
bool found = dfs(board, word, r+1, c, i+1) || dfs(board, word, r-1, c, i+1)
|| dfs(board, word, r, c+1, i+1) || dfs(board, word, r, c-1, i+1);
board[r][c] = ch; // 回溯还原
return found;
}
bool exist(vector<vector<char>>& board, string word) {
m = board.size(); n = board[0].size();
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (dfs(board, word, r, c, 0)) return true;
return false;
}
};Java
class Solution {
int m, n;
public boolean exist(char[][] board, String word) {
m = board.length; n = board[0].length;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (dfs(board, word, r, c, 0)) return true;
return false;
}
boolean dfs(char[][] board, String word, int r, int c, int i) {
if (i == word.length()) return true;
if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(i)) return false;
char ch = board[r][c];
board[r][c] = '#'; // 占位防重复走
boolean found = dfs(board, word, r+1, c, i+1) || dfs(board, word, r-1, c, i+1)
|| dfs(board, word, r, c+1, i+1) || dfs(board, word, r, c-1, i+1);
board[r][c] = ch; // 回溯还原
return found;
}
}套路模板 · 网格回溯（背下来）
def dfs(i, j, 状态):
if 当前格失败: return False # 剪枝
if 到达成功条件: return True
标记(i, j) = 占位符 # 占住
for ni, nj in 四个相邻方向:
if 不越界 and 未被占住:
if dfs(ni, nj, 新状态): return True
还原(i, j) = 原值 # 撤销标记（回溯）
return Falsebool dfs(grid, word, r, c, i) {
if (i == word.size()) return true; // 全匹配
if (越界 || grid[r][c] != word[i]) return false; // 不匹配/越界
char ch = grid[r][c]; grid[r][c] = '#'; // 占位
bool ok = dfs(r±1,c,i+1) || dfs(r,c±1,i+1); // 四向
grid[r][c] = ch; // 回溯还原
return ok;
}boolean dfs(grid, word, r, c, i) {
if (i == word.length()) return true; // 全匹配
if (越界 || grid[r][c] != word.charAt(i)) return false;
char ch = grid[r][c]; grid[r][c] = ＿; // 占位 #
boolean ok = dfs(r±1,c,i+1) || dfs(r,c±1,i+1); // 四向
grid[r][c] = ch; // 回溯还原
return ok;
}复杂度
时间复杂度
O(m·n·4^L)
m·n 个起点，每步最多 4 个方向，深度 L
空间复杂度
O(L)
递归栈深度 = 单词长度 L
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 单词搜索 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么回溯时要恢复格子标记？+
一个格子在这条路径用过、在别的起点/路径里还能用；只在「当前路径」内禁止重复，所以返回时撤销标记。
怎么剪枝？+
首字符不匹配的起点直接跳过；越界或字符不符立即返回 false。
复杂度？+
最坏 O(m·n·4^L)，L 是单词长度。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。