共计 2101 个字符,预计需要花费 6 分钟才能阅读完成。
【Leetcode 346/700】79. 单词搜寻【中等】回溯深度搜寻 JavaScript 版
1. 题目
n 二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中,返回 true;否则,返回 false。
单词必须依照字母程序,通过相邻的单元格内的字母形成,其中“相邻”单元格是那些程度相邻或垂直相邻的单元格。同一个单元格内的字母不容许被重复使用。
示例 1:
输出:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输入:true
示例 2:
输出:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输入:true
示例 3:
输出:board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输入:false
提醒:
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
2 解题思路
1. 遍历 board 所有元素,找到 word 的第一个雷同的元素,并且进行标记(marked), 进入递归去找接下来的第二个字符,接着第三个字母。如果没找到,返回 false;
- 在设定的边界内进行回溯搜寻,即上下左右进行搜寻下一个字符。找到了进入新的递归,没有找到的话,间接返回 false;
3. 解题留神点
1. 及时进行标记字符的状态,是曾经拜访了,还是未拜访;
2. 如果最初所有的字符串截取完了,阐明曾经找到合乎的答案啦,间接返回 true;
4. 解题代码
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function (board, word) {let border = [[0, 1], [0, -1], [1, 0], [-1, 0]], // 定义上下左右四个方向
col = board.length, // 行数
row = board[0].length, // 列数
marked = [...Array(col)].map(v => Array(row).fill()); // 同行列空矩阵,用于记录曾经拜访的
// 空数组间接返回 false
if (!col) return false;
let backTracing = (i, j, markeds, boards, words) => {
// 截取所有的字符,阐明曾经找到
if (!words.length) {return true;}
for (let p = 0; p < border.length; p++) {let curi = i + border[p][0]; // 左右方向
let curj = j + border[p][1]; // 高低方向
// 判断边界,且找到了第一个字符
if ((curi >= 0 && curi < col) && (curj >= 0 && curj < row && boards[curi][curj] == words[0])) {
// 曾经用过,间接跳过
if (markeds[curi][curj] == 1) {continue}
// 标记为已应用
markeds[curi][curj] = 1;
// 接着找下一个字符
if (backTracing(curi, curj, markeds, boards, words.substring(1))) {return true} else {
// 应用完重置掉
markeds[curi][curj] = 0;
}
}
}
return false
}
for (let i = 0; i < col; i++) {for (let j = 0; j < row; j++) {if (board[i][j] === word[0]) {
// 找到第一个字符,标记为曾经应用
marked[i][j] = 1;
// 进入回溯
if (backTracing(i, j, marked, board, word.substring(1))) {return true} else {
// 重置状态
marked[i][j] = 0;
}
}
}
}
return false
};
// 测试用例 1
let board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "ABCCED";
// 测试用例 2
let board1 = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word1 = "SEE"
// 测试用例 3
let board2 = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word2 = "ABCB"
console.log(exist(board, word)) //true
console.log(exist(board1, word1)) //true
console.log(exist(board2, word2)) //false
正文完
发表至: javascript
2022-05-13