欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【亡羊补牢】挑战数据结构与算法 第20期 LeetCode 79. 单词搜索(递归与回溯)

程序员文章站 2022-06-03 13:52:09
...

【亡羊补牢】挑战数据结构与算法 第20期 LeetCode 79. 单词搜索(递归与回溯)

仰望星空的人,不应该被嘲笑

题目描述

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

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

示例:

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

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

提示:

board 和 word 中只包含大写和小写英文字母。
1 <= board.length <= 200
1 <= board[i].length <= 200
1 <= word.length <= 10^3

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

解题思路

上一期做了单词搜索2 hard 版本之后,这道题也想用字典树玩一玩,没想到超时了,后面一想,数据确实有点大,而且对于一个单词来说,建立一颗字典树岂不是很浪费,还要花时间码代码…

本题也是回溯的思路,不过期间做了一点小优化,还是通过动态更改当前所走的格子,省去了那份 开辟vis 数组的空间。

对于递归层次,由于最后一次计算时,层次多算了一次(即多加了一次),所以条件为 >

【亡羊补牢】挑战数据结构与算法 第20期 LeetCode 79. 单词搜索(递归与回溯)

var exist = function(grid, word) {
  let dfs = (x,y,t) => {
    // 最后一次还会 +1 因此,条件是大于
    if(t > word.length-1){
      return true
    }
    // 剪枝条件
    if(x<0 || x>=grid.length || y<0 || y>=grid[0].length || grid[x][y]!= word[t] || grid[x][y] == '#') return false
    let tmp = grid[x][y]
    // 开始走
    grid[x][y] = '#'
    // 从四个方向搜索,只要一个方向搜索有结果,那么直接返回 true即可
    let res = dfs(x+1,y,t+1) || dfs(x,y+1,t+1) || dfs(x-1,y,t+1) || dfs(x,y-1,t+1)
    if(res) return true
    // 回溯(重置)
    grid[x][y] = tmp
    return false
  }
  for(let i=0;i<grid.length;i++){
    for(let j=0;j<grid[0].length;j++){
      if(grid[i][j] == word[0]){
        let res = dfs(i,j,0)
        if(res) return true
      }
    }
  }
  return false
};

最后

文章产出不易,还望各位小伙伴们支持一波!

往期精选:

小狮子前端の笔记仓库

访问超逸の博客,方便小伙伴阅读玩耍~

【亡羊补牢】挑战数据结构与算法 第20期 LeetCode 79. 单词搜索(递归与回溯)

学如逆水行舟,不进则退