sl1673495 / leetcode-javascript

:beers: 喝杯小酒,一起做题。前端攻城狮从零入门算法的宝藏题库,根据知名算法老师的经验总结了 100+ 道 LeetCode 力扣的经典题型 JavaScript 题解和思路。已按题目类型分 label,一起加油。
2.08k stars 344 forks source link

单词搜索-79 #77

Open sl1673495 opened 4 years ago

sl1673495 commented 4 years ago

给定一个二维网格和一个单词,找出该单词是否存在于网格中。

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

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/word-search 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

这是一个比较经典的可以用递归回溯法来解决的二维数组问题,这里用到几个技巧:

  1. [[-1, 0], [1, 0], [0, -1], [0, 1]] 这样的数组来标记访问 左、右、上、下 位置需要偏移的坐标量。
  2. 用和目标数组结构完全一致的二维数组 visited 来标记已访问过的元素,防止在递归的过程中重复访问,陷入死循环。
  3. 用一个 inArea 函数来判断接下来要访问的元素是否超出整个二维数组的边界。

递归函数

有了这些辅助方法后,接下来就需要创建一个递归函数 search,它接受的参数为:

  1. startX:本次匹配字符的起始 X 坐标。
  2. startY:本次匹配字符的起始 Y 坐标。
  3. wordIndex:本次需要匹配的字符串下标,在前一个下标已经成功匹配后才会进一步累加。

在这个递归函数中,如果当前的 xy 在二维数组中对应的字符和 wordIndex 所对应的字符匹配一致的话,并且 wordIndex 还没有到字符串的最后一位的话,就继续递归的向 上、下、左、右四个方向进一步递归匹配字符串的下一个下标 wordIndex + 1即可。

wordIndex 成功的来到字符串的最后一位下标后,即可根据最后一位字符是否匹配当前的 xy 来决定本次整个递归的返回值。

主函数

主函数中,只需要遍历整个二维数组,不断的以当前的坐标和 wordIndex = 0 开始从第一个字符遍历,只要 search 函数返回 true,就说明匹配成功,整体返回 true 结果即可。

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
let directions = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
] // 左 右 上 下

let exist = function (board, word) {
  let maxY = board.length
  if (!maxY) return false
  let maxX = board[0].length

  // 二维数组记录已访问过的元素
  let visited = new Array(maxY)
  for (let y = 0; y < visited.length; y++) {
    visited[y] = new Array(maxX)
  }

  let inArea = (x, y) => {
    return x >= 0 && x < maxX && y >= 0 && y < maxY
  }

  let search = (startX, startY, wordIndex) => {
    // 当前起始字符不匹配 直接失败
    let curCell = board[startY][startX]
    let curChar = word[wordIndex]
    if (curCell !== curChar) {
      return false
    }

    // 如果递归到最后一位字符 就直接返回最后一位字符是否匹配成功
    if (wordIndex === word.length - 1) {
      return curChar === curChar
    }

    // 进一步递归 先记录为已访问元素 防止递归的时候重复访问
    visited[startY][startX] = true

    for (let direction of directions) {
      let [x, y] = direction
      let nextX = startX + x
      let nextY = startY + y

      // 需要保证未越界且未被访问过
      if (inArea(nextX, nextY) && !visited[nextY][nextX]) {
        if (search(nextX, nextY, wordIndex + 1)) {
          return true
        }
      }
    }
    // 重置已访问标记位
    visited[startY][startX] = false
  }

  for (let y = 0; y < maxY; y++) {
    for (let x = 0; x < maxX; x++) {
      if (search(x, y, 0)) {
        return true
      }
    }
  }

  return false
}