Leetcode79单词搜索(深度遍历解法)

Leetcode79单词搜索(深度遍历解法)

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

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

```

/**

* @param {character[][]} board

* @param {string} word

* @return {boolean}

*/

const point = [0, -1, 0, 1, 0];

var exist = function (board, word) {

//如果word中有board中没有出现过的字母直接返回false;

const str = [...new Set(board.flat())].join('');

for(let ch of word){

if(!str.includes(ch)) return false;

}

const lenRow = board.length;

const lenCol = board[0].length;

const length = word.length;

function dfs(i, j, step) {

if (step === length) return true //如果step步数能走length步 返回true;

if (i < 0 || j < 0 || i >= lenRow || j >= lenCol || board[i][j] === 0) return false

const cur = board[i][j]

//如果当前字母与step步的字母不一致 返回false;

if(cur !== word[step]) return false;

board[i][j] = 0

let flag = false;

for(let k=0; k<=3; k++) {

const [ni, nj] = [i+point[k], j+point[k+1]];

flag ||= dfs(ni,nj,step+1); //看四个方向上有没有至少一个true ,能走完;

}

board[i][j] = cu

return flag

}

const first = word[0];

for (let i = 0; i < lenRow; i++) {

for (let j = 0; j < lenCol; j++) {

if (first === board[i][j] && dfs(i, j, 0)) {

return true

}

}

}

return false

}

```

解题思路：

深度遍历，遍历的时候把遍历的步数也传进去，同时遍历过的数组要置为0。

当遍历完成后再恢复，避免影响到后续的数组遍历。