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 当前点的坐标, idx 为局部索引
  const dfs = (row, col, idx) => {
    // 递归的出口: idx 越界了就返回 true
    if (idx === word.length) return true

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

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

    return isExist
  }

  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      // 从能匹配单词第一个字母的
      if (board[i][j] === word[0]) {
        if (dfs(i, j, 0)) {
          return true
        }
      }
    }
  }

  return false
}