复盘 · LC 79 单词搜索

题目

题号：LeetCode 79
名称：单词搜索（Word Search）
难度：Medium
链接：leetcode.cn/problems/word-search/
今日代码：79-单词搜索/index.js

题意

在 m × n 字符网格里，判断能否走出一条路径拼出 word。

每次只能上下左右走一格，不能重复使用同一格子。
路径不必用完整张板，只要拼出单词即可。
边界：word 长度为 1；起点很多但路径很快死掉；板很大、词很长时要注意剪枝。

涉及算法

标签	一句话
网格 DFS + 回溯	选邻格 → 标记已用 → 递归 → 撤销标记
四方向枚举	`[[-1,0],[1,0],[0,-1],[0,1]]` 模板

教程对照：19 · 递归心智与回溯框架（做选择 / 撤销）；网格走法与 200. 岛屿数量同族，差别是「可撤销」而不是「沉岛」。

评价我的解法

思路正确：先扫起点字母，再四向深搜 + visited 回溯；找到后用 res 提前停，能 AC（约 60%）。函数名叫 bfs 其实是 DFS——和昨天电话号码题同一命名习惯，面试口述会被纠。

我的代码（摘自 79-单词搜索/index.js，不含测例与提交统计）：

javascript

var exist = function (board, word) {
  /* col */
  const iLen = board.length;
  /* row */
  const jLen = board[0].length;
  /* wordArr */
  const wordArr = word.split("");
  /* firstLetter */
  const firstLetterArr = [];
  for (let i = 0; i < iLen; i++) {
    for (let j = 0; j < jLen; j++) {
      if (board[i][j] === wordArr[0]) {
        firstLetterArr.push({ i, j });
      }
    }
  }
  const dirArr = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  function isLegal(i, j) {
    return i >= 0 && j >= 0 && i < iLen && j < jLen;
  }
  let res = false;
  let isVisitGrid = Array.from({ length: iLen }).fill([]);
  isVisitGrid.forEach((_, index) => {
    isVisitGrid[index] = Array.from({ length: jLen }).fill(false);
  });
  function bfs(i, j, index) {
    if (res) {
      return;
    }
    if (index === wordArr.length) {
      res = true;
      return;
    }
    isVisitGrid[i][j] = true;
    for (let [di, dj] of dirArr) {
      const newI = i + di;
      const newJ = j + dj;
      if (
        isLegal(newI, newJ) &&
        !isVisitGrid[newI][newJ] &&
        board[newI][newJ] === wordArr[index]
      ) {
        bfs(newI, newJ, index + 1);
      }
    }
    isVisitGrid[i][j] = false;
  }
  for (const { i, j } of firstLetterArr) {
    bfs(i, j, 1);
  }
  return res;
};

对在哪：

回溯骨架对：进格 true、出格 false，不会串路径。
起点预筛：只从首字母开搜，少开无用分支。
命中短路：res 为真后不再展开，实用。

糙 / 可改：

命名：bfs → dfs；注释里 col/row 和 iLen/jLen 反了（board.length 是行数）。
visited 初始化绕：fill([]) 再 forEach 换行，直接 Array.from({length:m}, () => Array(n).fill(false)) 更清晰。
不必 split：下标读 word[index] 即可。
入口略别扭：从起点调用 dfs(i,j,1) 依赖「先匹配了 word[0]」；更常见写法是外层对每个格子调 dfs(i,j,0)，函数开头先校验当前格是否等于 word[0]。两种都能过，后者更统一。
复杂度：最坏仍指数级；可加字符频次剪枝（词里某字母多于板上），大盘面时有用。

小结：网格回溯的核心你已经会了；下一刀是命名与入口统一成「对每个起点 dfs(i,j,0)」。

最佳题解

标准网格 DFS（原地改板或 visited 均可；下面用改板省空间）：

javascript

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  const m = board.length;
  const n = board[0].length;
  const dirs = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  function dfs(i, j, k) {
    if (k === word.length) return true;
    if (i < 0 || j < 0 || i >= m || j >= n || board[i][j] !== word[k]) {
      return false;
    }
    const bak = board[i][j];
    board[i][j] = "#";
    for (const [di, dj] of dirs) {
      if (dfs(i + di, j + dj, k + 1)) {
        board[i][j] = bak;
        return true;
      }
    }
    board[i][j] = bak;
    return false;
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (dfs(i, j, 0)) return true;
    }
  }
  return false;
};

时间 O(m·n·4^L)（L = 词长），空间 O(L) 递归栈（原地标记无额外 visited）。
为何更优：入口统一、命中立即层层 return true、少一层 firstLetterArr 与全局 res。

关联题目

题	为何相关
212. 单词搜索 II	多词 → Trie + 同一套网格 DFS
200. 岛屿数量	网格 DFS，但一般不撤销
78. 子集	同一套「选 / 撤」心智，换到一维

一句话带走

单词搜索 = 四向 DFS + 进标记出撤销；函数名别叫 bfs，入口写成 dfs(i, j, 0)。

复盘 · LC 79 单词搜索 ​

题目 ​

题意 ​

涉及算法 ​

评价我的解法 ​

最佳题解 ​

关联题目 ​

一句话带走 ​