题目描述
判断单词能否在网格里相邻连续拼出(同一格不能重复用)。
board = A B / C D
word = "ABD"
输出 = true
思路解析
从匹配首字母的格子出发，逐字符向四个方向 DFS。走过的格子临时标记「用过」防止重复；某方向走不通就撤销标记、退回换方向。任一条路拼全单词就成功。
起点 (0,0) = A：扫到 (0,0)=A，和单词首字母 'A' 匹配，从这里开始 DFS。
标记 A · 找下一个 B：把 (0,0) 标记为已用(灰)。向四周找 'B'：右边 (0,1)=B 匹配，走过去。
标记 B · 找下一个 D：标记 (0,1)=B。向四周找 'D'：下方 (1,1)=D 匹配，走过去。
匹配完成：(1,1)=D 是单词最后一个字符，全部匹配成功，返回 true。(若中途断了，会回溯撤销标记、换方向或换起点)
关键在「撤销」：一条路探完(无论成败)，要把沿途格子的「用过」标记清掉，这样别的起点/方向还能再用这些格子。
「在网格里搜一条满足条件的路径」都是网格回溯：标记防重复、走不通就撤销回退。岛屿、迷宫、最长递增路径都沾边。
参考代码（Python）
Python
1def dfs(i, j, k): # k: 匹配到第几个字符
2 if board[i][j] != word[k]: return False
3 if k == len(word) - 1: return True # 全部匹配
4 tmp, board[i][j] = board[i][j], class="cl-str">"#" # 标记用过
5 found = any(dfs(ni, nj, k+1) for 四个相邻不越界)
6 board[i][j] = tmp # 撤销(回溯)
7 return found
8return any(dfs(i, j, 0) for 每个格子)复杂度分析
- 时间复杂度：O(m·n·4^L) —— L 是单词长度
- 空间复杂度：O(L) —— 递归深度
套路模板
记住骨架：失败/成功先判、标记、四向递归、撤销标记。「标记 + 撤销」配对出现，是网格回溯不出错的关键。
Python
1def dfs(i, j, 状态):
2 if 失败条件: return False
3 if 成功条件: return True
4 标记(i, j) # 占用
5 ok = any(dfs(ni,nj,新状态) for 四邻不越界且未用)
6 撤销标记(i, j) # 回溯!
7 return ok易错点
- ❌ 走过的格子不标记 → ✅ 进入就临时标记(如改成 #)（否则会原地来回、重复使用同一格）
- ❌ 递归后忘了撤销 → ✅ 返回前恢复原值（不撤销会污染其它起点的搜索）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。