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] = cur
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。
当遍历实现后再复原,防止影响到后续的数组遍历。