leetcode-javascript
leetcode-javascript copied to clipboard
单词搜索-79
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/word-search 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
这是一个比较经典的可以用递归回溯法来解决的二维数组问题,这里用到几个技巧:
- 用
[[-1, 0], [1, 0], [0, -1], [0, 1]]
这样的数组来标记访问左、右、上、下
位置需要偏移的坐标量。 - 用和目标数组结构完全一致的二维数组
visited
来标记已访问过的元素,防止在递归的过程中重复访问,陷入死循环。 - 用一个
inArea
函数来判断接下来要访问的元素是否超出整个二维数组的边界。
递归函数
有了这些辅助方法后,接下来就需要创建一个递归函数 search
,它接受的参数为:
-
startX
:本次匹配字符的起始 X 坐标。 -
startY
:本次匹配字符的起始 Y 坐标。 -
wordIndex
:本次需要匹配的字符串下标,在前一个下标已经成功匹配后才会进一步累加。
在这个递归函数中,如果当前的 x
、y
在二维数组中对应的字符和 wordIndex
所对应的字符匹配一致的话,并且 wordIndex
还没有到字符串的最后一位的话,就继续递归的向 上、下、左、右
四个方向进一步递归匹配字符串的下一个下标 wordIndex + 1
即可。
当 wordIndex
成功的来到字符串的最后一位下标后,即可根据最后一位字符是否匹配当前的 x
、y
来决定本次整个递归的返回值。
主函数
主函数中,只需要遍历整个二维数组,不断的以当前的坐标和 wordIndex = 0
开始从第一个字符遍历,只要 search
函数返回 true,就说明匹配成功,整体返回 true 结果即可。
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
let directions = [
[-1, 0],
[1, 0],
[0, -1],
[0, 1],
] // 左 右 上 下
let exist = function (board, word) {
let maxY = board.length
if (!maxY) return false
let maxX = board[0].length
// 二维数组记录已访问过的元素
let visited = new Array(maxY)
for (let y = 0; y < visited.length; y++) {
visited[y] = new Array(maxX)
}
let inArea = (x, y) => {
return x >= 0 && x < maxX && y >= 0 && y < maxY
}
let search = (startX, startY, wordIndex) => {
// 当前起始字符不匹配 直接失败
let curCell = board[startY][startX]
let curChar = word[wordIndex]
if (curCell !== curChar) {
return false
}
// 如果递归到最后一位字符 就直接返回最后一位字符是否匹配成功
if (wordIndex === word.length - 1) {
return curChar === curChar
}
// 进一步递归 先记录为已访问元素 防止递归的时候重复访问
visited[startY][startX] = true
for (let direction of directions) {
let [x, y] = direction
let nextX = startX + x
let nextY = startY + y
// 需要保证未越界且未被访问过
if (inArea(nextX, nextY) && !visited[nextY][nextX]) {
if (search(nextX, nextY, wordIndex + 1)) {
return true
}
}
}
// 重置已访问标记位
visited[startY][startX] = false
}
for (let y = 0; y < maxY; y++) {
for (let x = 0; x < maxX; x++) {
if (search(x, y, 0)) {
return true
}
}
}
return false
}