Skip to main content

单词搜索

Tips

题目类型: BackTracking

题目​

给定一个 m * n 二维字符网格 board 和一个字符串单词 word. 如果 word 存在于网格中, 返回 true; 否则, 返回 false.

单词必须按照字母顺序, 通过相邻的单元格内的字母构成, 其中 ß"相邻"单元格是那些水平相邻或垂直相邻的单元格. 同一个单元格内的字母不允许被重复使用.

提示:
  • m == board.length
  • n = board[i].length
  • 1 <= m, n <= 6
  • 1 <= word.length <= 15
  • board 和 word 仅由大小写英文字母组成

79-exist

题解​

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  const m = board.length
  const n = board[0].length
  const visited = new Array(m).fill(false).map(() => new Array(n).fill(false))

  // row 和 col 当前点的坐标, i 当前考察的 word 字符索引
  const dfs = (row, col, i) => {
    // 递归的出口: i 越界了就返回 true
    if (i === word.length) return true

    // 1. 当前点越界
    // 2. 或者当前点已经访问过
    // 3. 或非目标点
    // 返回 false
    if (
      row < 0 ||
      row >= m ||
      col < 0 ||
      col >= n ||
      visited[row][col] ||
      board[row][col] !== word[i]
    ) {
      return false
    }

    visited[row][col] = true
    const res =
      dfs(row + 1, col, i + 1) ||
      dfs(row - 1, col, i + 1) ||
      dfs(row, col + 1, i + 1) ||
      dfs(row, col - 1, i + 1)
    visited[row][col] = false

    return res
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      // 提前判断入口, 如果连 word 的第一个字符都匹配不上, 就没必要进入递归了
      if (board[row][col] === word[0] && dfs(i, j, 0)) return true
    }
  }

  return false
}