单词搜索

回溯与搜索 · 网格 DFS

在字母网格里拼出一个单词

给一张字母网格和一个目标单词，问能不能沿上下左右相邻、且同一个格子不重复使用的路径把单词拼出来。它和迷宫寻路 / 岛屿数量同样是网格 DFS，但目标又不一样：迷宫找一条路、岛屿数连通块、单词搜索沿着匹配的字母找路径——而且这是三者里最贴合回溯本义的一种。

试探 → 失败 → 撤销 → 回退

从某个等于单词首字母的格子出发做 DFS：当前格的字母对上了，就把它标记为已用（防止同一路径重复走），然后往四个方向找下一个字母；某个方向的字母不符就换方向；如果一个格子四个方向都走不通，说明此路不通——撤销刚才的标记、回退到上一格，接着试它剩下的方向。「撤销标记」这一步就是回溯的灵魂：回退后这个格子又能被别的路径使用了，这和迷宫的 visited（一路累积、不撤销）正相反。

下面固定一张 3×4 网格、目标词 ADEE。点「下一步」逐步看：琥珀环是当前探查的格、琥珀路径是已匹配的字母串；留意开头——从左上角 A(0,0) 出发找不到相邻的 D，此路不通、撤销回退，换第二个 A(2,0) 起点，沿底行A→D→E→E 一路匹配成功，整条路径变绿。右侧代码随每一步同步高亮。

从 (0,0)='A' 出发作为 "ADEE" 的首字母起点

1function exist(board: string[][], word: string): boolean {
const R = board.length, C = board[0].length;
const dfs = (r: number, c: number, k: number): boolean => {
  if (board[r][c] !== word[k]) return false;      // 字母不符
  if (k === word.length - 1) return true;         // 拼完 → 命中
  const tmp = board[r][c]; board[r][c] = '#';      // 标记已用（防复用）
  for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
    const nr = r + dr, nc = c + dc;
    if (nr >= 0 && nr < R && nc >= 0 && nc < C &&
        dfs(nr, nc, k + 1)) { board[r][c] = tmp; return true; }
  }
  board[r][c] = tmp;                              // 撤销标记，回溯
  return false;
};
for (let r = 0; r < R; r++)
  for (let c = 0; c < C; c++)
    if (dfs(r, c, 0)) return true;                // 从每个格子尝试起点
return false;
19}

网格: 3×4 字母
目标词: ADEE
已匹配: A
当前格: (0,0)='A'
路径长: 1

单词搜索和 N 皇后 / 子集 / 组合总和是同一套回溯骨架，只是状态空间从棋盘、决策树换成了网格路径——「进入时标记、离开时撤销」让搜索能穷举而不越界。

单词搜索在哪里用

拼字游戏 / Boggle：判断能否在字母盘上连出某个词。
路径约束搜索：迷宫带钥匙、网格收集序列、棋盘连线消除。
进阶：一次找很多单词时，用前缀树 Trie 把所有词组织起来一起搜（单词搜索 II），避免对每个词各扫一遍。

至此网格搜索三形态齐了：迷宫（找一条路）、岛屿（数连通块）、单词搜索（带回溯的路径匹配）——同一张网格、同一套 DFS，目标不同、玩法各异。