单词搜索
回溯与搜索 · 网格 DFS
在字母网格里拼出一个单词
给一张字母网格和一个目标单词，问能不能沿上下左右相邻、且同一个格子不重复使用的路径把单词拼出来。它和 迷宫寻路 / 岛屿数量同样是网格 DFS，但目标又不一样：迷宫找一条路、岛屿数连通块、单词搜索沿着匹配的字母找路径——而且这是三者里最贴合回溯本义的一种。
试探 → 失败 → 撤销 → 回退
从某个等于单词首字母的格子出发做 DFS：当前格的字母对上了，就把它标记为已用（防止同一路径重复走），然后往四个方向找下一个字母；某个方向的字母不符就换方向；如果一个格子四个方向都走不通，说明此路不通——撤销刚才的标记、回退到上一格，接着试它剩下的方向。「撤销标记」这一步就是回溯的灵魂：回退后这个格子又能被别的路径使用了，这和迷宫的 visited（一路累积、不撤销）正相反。
下面固定一张 3×4 网格、目标词 ADEE。点「下一步」逐步看：琥珀环是当前探查的格、琥珀路径是已匹配的字母串；留意开头——从左上角 A(0,0) 出发找不到相邻的 D，此路不通、撤销回退，换第二个 A(2,0) 起点，沿底行A→D→E→E 一路匹配成功，整条路径变绿。右侧代码随每一步同步高亮。
A
B
C
E
S
F
C
S
A
D
E
E
从 (0,0)='A' 出发作为 "ADEE" 的首字母起点
1function exist(board: string[][], word: string): boolean {
2 const R = board.length, C = board[0].length;
3 const dfs = (r: number, c: number, k: number): boolean => {
4 if (board[r][c] !== word[k]) return false; // 字母不符
5 if (k === word.length - 1) return true; // 拼完 → 命中
6 const tmp = board[r][c]; board[r][c] = '#'; // 标记已用（防复用）
7 for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
8 const nr = r + dr, nc = c + dc;
9 if (nr >= 0 && nr < R && nc >= 0 && nc < C &&
10 dfs(nr, nc, k + 1)) { board[r][c] = tmp; return true; }
11 }
12 board[r][c] = tmp; // 撤销标记，回溯
13 return false;
14 };
15 for (let r = 0; r < R; r++)
16 for (let c = 0; c < C; c++)
17 if (dfs(r, c, 0)) return true; // 从每个格子尝试起点
18 return false;
19}
网格3×4 字母
目标词ADEE
已匹配A
当前格(0,0)='A'
路径长1
1 / 11
单词搜索和 N 皇后 / 子集 / 组合总和 是同一套回溯骨架，只是状态空间从棋盘、决策树换成了网格路径——「进入时标记、离开时撤销」让搜索能穷举而不越界。
单词搜索在哪里用
拼字游戏 / Boggle：判断能否在字母盘上连出某个词。
路径约束搜索：迷宫带钥匙、网格收集序列、棋盘连线消除。
进阶：一次找很多单词时，用 前缀树 Trie 把所有词组织起来一起搜（单词搜索 II），避免对每个词各扫一遍。
路径约束搜索：迷宫带钥匙、网格收集序列、棋盘连线消除。
进阶：一次找很多单词时，用 前缀树 Trie 把所有词组织起来一起搜（单词搜索 II），避免对每个词各扫一遍。
至此网格搜索三形态齐了：迷宫（找一条路）、岛屿（数连通块）、单词搜索（带回溯的路径匹配）——同一张网格、同一套 DFS，目标不同、玩法各异。