前端刷题路-Day18|刷题打卡

我心飞翔 分类:javascript

掘金团队号上线,助你 Offer 临门! 点击 查看详情

单词搜索(题号79)

题目

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

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

示例 1:

img

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出:true
 

示例 2:

img

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出:true
 

示例 3:

img

输入:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出:false
 

提示:

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

链接

leetcode-cn.com/problems/wo…

解释

这题本来自己都快做出来了,可有一个巨长的测试用例就是过不了,百思不得其解,逻辑明明没有任何问题,小型测试用例也没问题,数据量一大就不行了,看了看操作,我和正确答案的区别就是它存走过的路径用的一个二维数组,而我用的一维数组,利用indexOf开判断当前位置是不是在里面,它直接利用i和j定位到而已。
事实证明,就是这里出的问题

自己的答案(GG)

var exist = function(board, word) {
  var wordArr = word.split('')
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] === wordArr[0]) {
        if (findMore(1, i, j, [`${i}${j}`])) {
          return true
        }
      }        
    }      
  }    
  function findMore(k, i, j, forbidArr) {
    if (k === wordArr.length) return true
    i += 1
    if (forbidArr.indexOf(`${i}${j}`) < 0 && board[i] && board[i][j] && board[i][j] === wordArr[k]) {
      forbidArr.push(`${i}${j}`)
      if (board[i][j] === wordArr[k] && findMore(k + 1, i, j, forbidArr)) {
        return true
      } else {
        forbidArr.pop()
      }
    }
    i -= 2
    if (forbidArr.indexOf(`${i}${j}`) < 0 && board[i] && board[i][j] && board[i][j] === wordArr[k]) {
      forbidArr.push(`${i}${j}`)
      if (board[i][j] === wordArr[k] && findMore(k + 1, i, j, forbidArr)) {
        return true
      } else {
        forbidArr.pop()
      }
    }
    i += 1
    j += 1
    if (forbidArr.indexOf(`${i}${j}`) < 0 && board[i] && board[i][j] && board[i][j] === wordArr[k]) {
      forbidArr.push(`${i}${j}`)
      if (board[i][j] === wordArr[k] && findMore(k + 1, i, j, forbidArr)) {
        return true
      } else {
        forbidArr.pop()
      }
    }
    j -= 2
    if (forbidArr.indexOf(`${i}${j}`) < 0 && board[i] && board[i][j] && board[i][j] === wordArr[k]) {
      forbidArr.push(`${i}${j}`)
      if (board[i][j] === wordArr[k] && findMore(k + 1, i, j, forbidArr)) {
        return true
      } else {
        forbidArr.pop()
      }
    }
    return false
  }
  return false
};
 

老实说,这个方法除了有点丑陋没啥缺点,确实有需要精简的部分,但也不至于跑不起来啊。迫不得已只能看了答案,结果就是上面解释说的了

自己的答案(回溯)

这是第二次做这题的答案了,正好上一题用到了回溯,这里也用回溯解决了问题👇:

var exist = function(board, word) {
  var len = board.length
      wid = board[0].length
      arr = Array.from({length: len}, () => (new Array(wid).fill(false)))
  function getBack(activeLocation, lastWord) {
    if (!lastWord) return true
    const [i, j] = activeLocation
    for (const [x, y] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
      if (arr[i + x] && !arr[i + x][j + y] && board[i + x][j + y] === lastWord[0]) {
        arr[i + x][j + y] = true
        if (getBack([i + x, j + y], lastWord.substr(1))) {
          return true
        } else {
          arr[i + x][j + y] = false
        }
      }
    }
    return false
  }
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < wid; j++) {
      if (board[i][j] === word[0]) {
        arr[i][j] = true
        if (getBack([i, j], word.substr(1))) {
          return true
        } else {
          arr[i][j] = false
        }
      }
    }
  }
  return false
};
 

其实感觉也还好,可能就是getBack这个方法有些问题,它应该再精简一点的,而且把是否存在的条件放到第一位,这样代码看上去会更简单一些,就像👇的findChart一样。

更好的方法(递归)

var exist = function(board, word) {
  var forbid = []
  for (let i = 0; i < board.length; i++) {
    forbid[i] = new Array(board[i].length)
  }
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] === word[0]) {
        if (findChart(0, i, j)) {
          return true
        }
      }
    }
  }
  function findChart(k, i, j) {
    if (k === word.length) return true;
    if (!board[i] || !board[i][j])  return false
    if (forbid[i][j] || board[i][j] !== word[k]) return false
    forbid[i][j] = true
    var findRes = findChart(k + 1, i + 1, j) ||  findChart(k + 1, i - 1, j) ||  findChart(k + 1, i, j + 1) ||  findChart(k + 1, i, j - 1)
    if (findRes) return true
    forbid[i][j] = false
    return false
  }
  return false
};
 

这个方法其实不是原答案,是我参考了部分解答后自己又操作了一波得出的结论,很有我的风格
但注意,这里的forbid是个二维数组,判断是否存在只需要利用index取值就好,不用indexOf来搜索,其实区别就这么点,结果他娘的还真就没问题了,令人发指

这里用

Why

为了进一步验证是indexOf的问题,特意写了个东西来测试执行用时

两次循环的次数都是一样的,2500次。indexOf利用Math.random来获取随机数,而change通过循环i和j来拿到不一样的值,为了抵消Math.random的影响,特意在change中加上了一行无用代码,结果十分出人意料,这差距也太明显了,耗时差了大概20倍,我的写法由于递归次数太多,在如此的耗时下GG也就有点正常了

var arr = []
for (let i = 0; i < 100; i++) {
  arr[i] = new Array(100)
  for (let j = 0; j < 100; j++) {
    arr[i][j] = `${i}${j}`
  }
}
var newArr = []
for (let i = 0; i < 10000; i++) {
  newArr.push(i)
}
console.time('indexOf')
for (let i = 0; i < 2500; i++) {
  var num = parseInt(Math.random() * 10000)
  var boolean = newArr.indexOf(num)
  newArr[999] = 'fun'
}
console.timeEnd('indexOf')
console.time('change')
for (let i = 0; i < 50; i++) {
  for (let j = 0; j < 50; j++) {
    var num = parseInt(Math.random() * 10000)
    var num = arr[i][j]
    arr[i][j] = 'fun'
  }
}
console.timeEnd('change')
 

indexOf: 13.716ms
change: 0.698ms

PS:想查看往期文章和题目可以点击下面的链接:

这里是按照日期分类的👇

前端刷题路-目录(日期分类)

经过有些朋友的提醒,感觉也应该按照题型分类
这里是按照题型分类的👇

前端刷题路-目录(题型分类)

有兴趣的也可以看看我的个人主页👇

Here is RZ

回复

我来回复
  • 暂无回复内容