79-单词搜索.md

题目描述

单词搜索

题目简述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

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

例如： board = [

["A","B","C","E"],

["S","F","C","S"],

["A","D","E","E"]

], word = "ABCCED"

输出为true

分类

中等 回溯

思路

回溯（类似n皇后思路）

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
  const arr = new Array(word.length).fill(null).map(() => [])
  board.forEach((row, rowIndex) => {
    row.forEach((point, columnIndex) => {
      const _point = {
        name: point,
        position: [rowIndex, columnIndex],
        wasted: false
      }
      // 所有的位置
      let index = word.indexOf(point)
      // 是存在于word中的
      while (index !== -1) {
        arr[index].push(_point)
        index = word.indexOf(point, index + 1)
      }
    })
  })
  // 如果arr中有空，则说明缺失某个字母
  if(arr.some(i => !i.length)) {
    return false
  }
  return existWorld(0)
  /**
   * 对arr做递归
   * @param {Number} index 第几个字母 
   * @param {Array} position 
   */
  function existWorld (index, position) {
    if (index === arr.length) {
      return true
    }
    // 位置校验，对arr[index]中的每一个进行校验
    for (let i = 0; i < arr[index].length; i++) {
      // 对比 arr[index][i].position position 而且不能是wasted
      // 第0个则不进行位置的校验
      if (index === 0 || !arr[index][i].wasted && judgePosition(arr[index][i].position, position)) {
        arr[index][i].wasted = true
        if (existWorld(index + 1, arr[index][i].position)) {
          return true
        }
        arr[index][i].wasted = false
      }
    }
    return false
    // arr[index]
  }

  /**
   * 判断两个点是否属于上下|左右关系，|x1-x2| + |y1-y2| === 1
   * @param {*} p1 
   * @param {*} p2 
   */
  function judgePosition (p1, p2) {
    return Math.abs(p1[0]-p2[0]) + Math.abs(p1[1]-p2[1]) === 1
  }
};

• 问题拆解

  • 首先生成一个数组arr，数组是一个二维数组，其中的arr[index]储存的是word字符串的第index个字符在网格中的所有体现。例如word是'arhcccd'，那么arr[0]就是储存的整个网格中的字母a的信息，具体信息被编码如下
    • 每个网格有以下几个属性
      • name 该网格的字母
      • position 网格坐标
      • wasted 是否已经使用
  • 通过对arr数组中元素进行遍历，选择第一个元素后，因为该元素被使用，将该元素的wasted置为true。再继续进行arr的下一次遍历，如果某个网格元素wasted === false，而且和当前元素处于相邻状态，即可行，进行下一次判断。最终只要能够进行到arr的最后一个元素完成，就说明能够找到。因为有可能某次的遍历到最后不能满足，就需要回溯后（将wasted置回false即可），尝试另一个相同的字符。
    • 例如arr = [[a, a], [b], [c, c]]，在arr[0][0]的字符a向后尝试后，无法找到结果，需要调用arr[0][1]尝试。
  • 判断两个位置的网格是否具有相邻关系
    • 很容易想到，两个点位要么x相差1，要么y相差1，所以Math.abs(p1[0]-p2[0]) + Math.abs(p1[1]-p2[1]) === 1即可

• 一些想法

  • 写这个文档的时候离做题过了一周,想法有些跟不上了，在代码的这里

    board.forEach((row, rowIndex) => {
      row.forEach((point, columnIndex) => {
        const _point = {
          name: point,
          position: [rowIndex, columnIndex],
          wasted: false
        }
        // 所有的位置
        let index = word.indexOf(point)
        // 是存在于word中的
        while (index !== -1) {
          arr[index].push(_point)
          index = word.indexOf(point, index + 1)
        }
      })
    })

    我还在想是不是能够把_point的定义放到while(index !== -1)里去，这样就只有在需要的时候才回去定义，应该是很好的优化🤔～

    然后我修改了提交代码，好家伙，不通过了。这不是一样的代码吗？？？思索一会才想起来我这里这么写是刻意的，试想一种情况word='aab'，那么我们的arr就是[[a, a], [a, a], [b]]，arr[0]和arr[1]中的字符应该保持一样的状态，否则我使用了arr[0][1]的a后，arr[1][1]的a的wasted字段还是false，仍然会被当作能够使用。所以我这里把_point写到外面是为了共用一个地址，一次使用，大家更新。