外观
单词搜索避坑实录：网格回溯与原地标记恢复
问题背景：为什么单词搜索是网格回溯经典题
单词搜索（Word Search）要求在一个二维字符网格中判断某个单词是否存在。路径可以从任意单元格开始，每一步只能向上、下、左、右移动，并且同一个单元格不能重复使用。
这类问题的本质是：在一个隐式图中寻找一条满足字符顺序的路径。网格中的每个格子都是节点，相邻格子之间有边。由于路径是否可行取决于当前已经匹配了多少字符，搜索过程天然带有“尝试—失败—撤销”的特征，因此非常适合使用 DFS 加回溯。
一个朴素想法是：从每个格子出发，只要字符匹配就继续向四个方向搜索。但如果不记录访问状态，就可能在递归中绕回已使用的格子；如果额外使用 visited 集合，又会带来额外空间和频繁的集合操作。单词搜索中最常用的优化技巧，就是把当前格子临时改成特殊字符，递归返回后再恢复，这就是“原地标记”。
方案对比：visited 集合与原地标记怎么选
常见实现有两种。
第一种是使用 visited 集合或二维布尔数组。进入格子时标记为已访问，递归结束后取消标记。它的语义清晰，适合刚接触回溯时理解状态变化，但每个递归分支都要维护额外结构，空间复杂度通常增加到 O(mn)。
第二种是原地标记。因为当前格子已经匹配成功，而题目字符通常是英文字母，所以可以临时把 board[i][j] 改成 '#' 或空字符串。后续递归看到特殊字符就知道该格子不可再次使用。递归返回前把原值写回即可。它不需要额外 visited 空间，递归栈之外的辅助空间为 O(1)。
需要注意，原地标记会修改输入网格，因此必须在递归结束后恢复。如果题目要求函数执行后 board 保持不变，恢复原值是必要步骤；即使不要求保持输入不变，不恢复也会污染其他起点的搜索，导致漏答案。
解题思路：先判定边界，再匹配、标记、搜索、恢复
可以把 DFS 函数设计为 dfs(row, col, index)，表示当前正在尝试让 grid[row][col] 匹配 word[index]。
递归终止条件有两个：
- 如果 index 等于单词长度，说明所有字符都已匹配，返回 True。
- 如果坐标越界、当前格子已被标记，或字符不等于 word[index]，返回 False。
单层递归流程如下：
- 保存当前字符 backup = board[row][col]。
- 将 board[row][col] 标记为 '#'，防止本路径重复进入。
- 依次搜索上、下、左、右四个方向，目标字符下标为 index + 1。
- 任一分支成功即可返回 True。
- 无论成功或失败，返回前都把 board[row][col] 恢复为 backup。
最外层枚举所有格子作为起点。只要有一个 DFS 返回 True，答案就是 True。
Python 可运行代码：含中文注释与提前剪枝
下面代码可以直接保存运行，包含核心解法和简单测试用例。
python
from typing import List
def exist(board: List[List[str]], word: str) -> bool:
"""判断 word 是否能由网格中相邻且不重复的单元格组成。"""
rows, cols = len(board), len(board[0])
def dfs(r: int, c: int, index: int) -> bool:
# 所有字符均已匹配
if index == len(word):
return True
# 越界、当前路径已使用、字符不匹配，均直接剪枝
if (
r < 0 or r >= rows
or c < 0 or c >= cols
or board[r][c] == '#'
or board[r][c] != word[index]
):
return False
# 原地标记：保存原值，递归后恢复
backup = board[r][c]
board[r][c] = '#'
# 四个方向使用短路求值，找到答案后不再继续搜索
found = (
dfs(r - 1, c, index + 1) or
dfs(r + 1, c, index + 1) or
dfs(r, c - 1, index + 1) or
dfs(r, c + 1, index + 1)
)
# 关键：撤销选择，避免污染其他递归分支
board[r][c] = backup
return found
# 可以从任意单元格开始
for r in range(rows):
for c in range(cols):
if dfs(r, c, 0):
return True
return False
# 测试用例
board = [
["A", "B", "C", "E"],
["S", "F", "C", "S"],
["A", "D", "E", "E"]
]
print(exist(board, "ABCCED")) # True
print(exist(board, "SEE")) # True
print(exist(board, "ABCB")) # False代码中使用 Python 的 or 进行短路搜索。只要某个方向成功，后面的方向不会继续执行，但恢复语句仍然会运行，这是因为恢复发生在 found 计算完成之后。
复杂度分析
设网格大小为 m × n，单词长度为 L。
时间复杂度最坏为 O(mn · 4^L)。每个格子都可能作为起点，每次搜索最多扩展四个方向。实际运行通常远小于这个上界，因为字符不匹配会立即剪枝，而且路径不能重复访问格子。当 L 大于网格总单元格数时，也可以直接返回 False。
空间复杂度为 O(L)，主要来自递归调用栈。原地标记没有使用额外 visited 数组；如果使用二维 visited 数组，则辅助空间会变成 O(mn + L)，通常写作 O(mn)。
还可以加入两个实用剪枝：
- 如果 word 为空，按常见定义返回 True。
- 如果单词长度大于 m × n，直接返回 False。
- 统计网格字符频率，若某个单词字符数量不足，直接返回 False。
频率剪枝对重复字符很多的极端用例尤其有效，但它属于入口优化，不替代核心回溯。
避坑总结：这些错误最容易导致 WA 或 TLE
1. 只标记不恢复，导致后续起点全部被污染
常见错误现象是单个分支看似能搜索，但换一个起点后答案变成 False。原因是递归失败后没有执行 board[r][c] = backup，网格中残留大量 '#'，其他路径无法再经过这些格子。
修正方法是把“标记”和“恢复”严格配对。不要只在成功分支恢复，因为失败分支也必须撤销选择。更稳妥的写法是先计算 found，再统一恢复，最后 return found。
2. 先递归再判断，造成下标越界或重复访问
有些写法在当前格子不判断边界，直接向四个方向调用 dfs，再在下一层处理。虽然理论上也能工作，但容易把 visited 判断和字符判断顺序写乱，例如访问 board[r][c] 时 r 已经越界。
修正方法是在 dfs 开头统一处理：先判断 index 是否完成，再判断坐标越界、标记状态和字符是否匹配。这样每个递归分支都有单一入口，逻辑更安全。
3. 忘记同一路径不能重复使用单元格
如果只根据相邻关系搜索，而不使用 visited 或原地标记，单词如 "AAA" 可能在两个 A 格子之间来回跳动，错误返回 True。题目明确要求同一个单元格不能重复使用。
修正方法是进入格子后立刻标记，递归返回时恢复。标记必须只在当前 DFS 路径中生效，不能在全局永久保留。
4. 方向搜索写成四条独立 if，找到答案后仍继续递归
这种写法结果未必一定错误，但会产生大量无效搜索，在大网格上容易超时。比如第一个方向已经找到完整单词，后面三个方向仍然继续展开。
修正方法是使用 found = 上 or 下 or 左 or 右，利用短路求值立即停止扩展；也可以逐个方向判断，一旦 found 为 True 就跳出循环，但别忘了最终仍要恢复当前格子。
5. 原地标记字符与题目输入字符冲突
大多数单词搜索题输入只包含大小写英文字母，使用 '#' 没问题。但如果题目允许任意字符，极端情况下 '#' 可能本身就是待匹配字符，造成错误拦截。
修正方法是先确认字符范围；在字符范围不确定时，使用与输入类型不冲突的标记，或改用 visited 集合。算法技巧要结合题面约束，不能机械照搬。
掌握“匹配当前格—原地标记—递归四方向—恢复现场”这套结构后，不仅能解决单词搜索，也能迁移到岛屿路径、矩阵中的字符串匹配、棋盘放置等二维回溯问题。核心不是记住模板，而是理解每个状态为什么要修改、什么时候必须撤销。
免责声明
本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。