原文:79. 单词搜索(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址:https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-079/

题目:

难度:Middle

相关话题:数组回溯算法

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

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

示例:

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

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

思路:

DFS搜索,对于每一个board[i][j]===word[0],都进行尝试,只要存在一个true,返回true

由于dfs过程中,使用visited,保存当前已经搜索过的路径,但每一次找到board[i][j]===word[0],相当于需要一个全新的visited

个人之前做法,设定一个uniq值,初始为0,每当找到board[i][j]===word[0],首先uniq++,每次检索路径visited[i][j]=uniq,检索完毕,visited[i][j]=uniq-1; 这样做,需要创建visited,但只需要创建一次。

更好的做法是,对于每次检索的路径,board[i][j]='*',检查完毕,再改回来,这么做的最大优点是节省空间。

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function(board, word) {
  let m=board.length,n=board[0].length
  let moves=[[-1,0],[1,0],[0,1],[0,-1]]
  let uniq=0
  function dfs([x,y],id){
    if(id===word.length)return true
    if(x<0 || y<0 || x>=m || y>=n)return
    if(board[x][y]!==word[id])return
    if(board[x][y]==='*')return
    let tmp=board[x][y]
    board[x][y]='*'
    for(let [dx,dy] of moves){
      if(dfs([x+dx,y+dy],id+1))return true
    }
    board[x][y]=tmp
  }
  let start=word[0]
  for(let i=0;i<m;i++){
    for(let j=0;j<n;j++){
      if(dfs([i,j],0))return true
    }
  }
  return false
};