单词搜索
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true；否则，返回 false。
单词必须按照字母顺序，通过水平或垂直相邻的单元格内的字母构成。同一个单元格内的字母不允许被重复使用。
示例 1
示例 2
示例 3
模拟答题者思考
1. 暴力直觉：从每个格子当起点，用 DFS 尝试拼出 word 的每个字母——方向只有上下左右，路径长度最多 L = len(word) ≤ 15，网格也仅 6×6，回溯可行。
2. 重复在哪里？同一条搜索路径不能两次经过同一格子；若只记坐标集合而不「撤销」，回溯到上一层时仍会误以为该格已用，漏掉其他合法路径。
3. 关键转化：把「已访问」绑在格子上——匹配 word[k] 时暂时把 board[r][c] 改成 '#'，返回前改回去；这样同一 DFS 栈内自然满足「不重复使用格子」。
4. 外层枚举：凡 board[r][c] == word[0] 的格子都可能是起点，任一 dfs(r,c,0) 为真即答案为真。
5. 剪枝：字符不等直接返回；L 很小，不必再建额外 visited 数组，原地标记最省空间。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
r, c | int | 定义：当前正在匹配的格子坐标 维护：DFS 每步只向四邻之一移动一格，且不出界 更新：从起点 (r,c) 出发，递归时传入邻居坐标 |
k | int | 定义：下一步要匹配的字符在 word 中的下标（当前已匹配 word[0..k-1]）维护：进入格子前要求 board[r][c] == word[k]；匹配成功后下一层传 k+1更新： k == len(word) 时整条路径匹配完成，返回成功 |
board[r][c] | char | 定义：网格字母；同时承担「是否已在本路径中使用」的标记 维护：进入 DFS 时暂改为占位符（如 '#'），回溯时恢复原字符，避免同一路径重复踩格更新：成功探索后必须还原，否则兄弟分支无法复用该格 |
落码步骤
1. 若 word 为空，按题意可视为 true（一般 len(word) ≥ 1）
2. 双重循环找所有 board[r][c] == word[0] 的起点，调用 dfs(r, c, 0)
3. dfs(r, c, k)：越界、格子为 '#'、或 board[r][c] != word[k] 则失败
4. 若 k == len(word) - 1，当前格是最后一个字母，返回 true
5. 保存 ch = board[r][c]，置 board[r][c] = '#'，四方向递归 dfs(..., k+1)
6. 任一方向成功则返回 true；否则恢复 board[r][c] = ch 并返回 false
代码实现
class Solution:
def exist(self, board: list[list[str]], word: str) -> bool:
m, n = len(board), len(board[0])
def dfs(r: int, c: int, k: int) -> bool:
if board[r][c] != word[k]:
return False
if k == len(word) - 1:
return True
ch = board[r][c]
board[r][c] = "#"
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and dfs(nr, nc, k + 1):
board[r][c] = ch
return True
board[r][c] = ch
return False
for r in range(m):
for c in range(n):
if board[r][c] == word[0] and dfs(r, c, 0):
return True
return Falseclass Solution {
int m, n;
bool dfs(vector<vector<char>>& board, int r, int c, const string& word, int k) {
if (board[r][c] != word[k])
return false;
if (k == (int)word.size() - 1)
return true;
char ch = board[r][c];
board[r][c] = '#';
const int dr[4] = {0, 0, 1, -1};
const int dc[4] = {1, -1, 0, 0};
for (int t = 0; t < 4; t++) {
int nr = r + dr[t], nc = c + dc[t];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && dfs(board, nr, nc, word, k + 1)) {
board[r][c] = ch;
return true;
}
}
board[r][c] = ch;
return false;
}
public:
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 (board[r][c] == word[0] && dfs(board, r, c, word, 0))
return true;
}
}
return false;
}
};
// 时间 O(m·n·3^L)，空间 O(L) 递归栈复杂度分析
O(m·n·3^L)（L 为 word 长度；首步四向、之后每步至多 3 向，m·n 为起点枚举）
O(L)（递归栈深度，不计原地改格子的临时标记）
常见坑
回溯未恢复格子：忘记把 '#' 改回原字符，会导致其他起点或分支误判「该格已用」。
终点判断：应在匹配当前格为 word[k] 后，若 k == len(word)-1 直接成功，避免无意义地向四邻继续搜。
用全局 visited 却不按层回溯：应随 DFS 撤销标记；更简洁的做法是原地改 board，与岛屿 DFS 类似。
必测边界 Case
board = [["A"]], word = "A" → true
board 中无 word[0] → false
word = "ABCB" → false（不能重复用同一 B）
多个 'S' 作起点时，应分别 DFS，任一成功即可
board = [["A"]], word = "B" → false