回溯
解题思路
backtrack 表示从任意位置出发，对比是否匹配 word 的第 inx 个字母；
backtrack 会向 上、下、左、右 四个方向搜索，搜索到返回 true ，反之返回 false；
为了防止重复遍历相同的位置，需要将当前的字符置 null ，用于标识这个位置被访问过，每次遍历相邻位置时，需要跳过已经被访问的位置，遍历完成后回撤，恢复原来的值；
终止条件：已经访问到字符串的末尾，且对应字符依然匹配；
剪枝：
- 索引越界；
- 当前元素 !== 指定字符；
图解
代码实现
function exist(board, word) {
if (word.length === 0) return true;
if (board.length === 0) return false;
let rowRange = board.length;
let colRange = board[0].length;
for (let rowInx = 0; rowInx < rowRange; rowInx++) {
for (let colInx = 0; colInx < colRange; colInx++) {
if (backtrack(board, word, rowRange, colRange, rowInx, colInx, 0)) return true;
}
}
return false;
};
/**
* @param {* string[][]} board n*n 的二维表格
* @param {* string} word 单词
* @param {* number} rowRange 行边界
* @param {* number} colRange 列边界
* @param {* number} rowInx 行索引
* @param {* number} colInx 列索引
* @param {* number} curInx word 的字母索引
* @returns boolean
*/
const backtrack = (board, word, rowRange, colRange, rowInx, colInx, curInx) => {
// 剪枝：索引越界
if (rowInx < 0 || colInx < 0 || rowInx >= rowRange || colInx >= colRange) return false;
// 剪枝：当前元素 !== 指定字符
if (board[rowInx][colInx] !== word[curInx]) return false;
// 结果：全部匹配，返回 true
if (curInx === word.length - 1) return true;
board[rowInx][colInx] = null; // 当前字母匹配后，将当前位置置空，避免之后被重复使用
// 向上下左右寻找下一个字母
const res =
backtrack(board, word, rowRange, colRange, rowInx + 1, colInx, curInx + 1) ||
backtrack(board, word, rowRange, colRange, rowInx - 1, colInx, curInx + 1) ||
backtrack(board, word, rowRange, colRange, rowInx, colInx + 1, curInx + 1) ||
backtrack(board, word, rowRange, colRange, rowInx, colInx - 1, curInx + 1);
// 回撤
board[rowInx][colInx] = word[curInx];
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 491. 非递减子序列
上一篇
评论
