题目:
难度: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
};