题目:
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
抛砖引玉
思路
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
let dir = [[0, 1], [0, -1], [1, 0], [-1, 0]],
len = word.length,
m = board.length,
n = board[0]?board[0].length:0,
visited = new Array(m);
// 初始化记录选择矩阵
for (let i = 0; i <m; ++i) {
visited[i] = Array(n).fill(false);
}
// 枚举起点
for(let i = 0;i<m;i++){
for(let j = 0;j<n;j++){
if(board[i][j] === word[0] && helper(0,[i,j])){
return true
}
}
}
// 匹配字符指针 上一个匹配上的位置坐标
function helper(index,[x,y]) {
let _result = false;
if(index === len-1) return true;
// 上一个匹配坐标标记已选
visited[x][y] = true
for (let [dx, dy] of dir) {
let nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
if (!visited[nx][ny]) {
if (board[nx][ny] === word[index+1] && helper(index + 1,[nx, ny])) {
_result = true;
break;
}
}
}
}
// 上一个匹配坐标起,枚举匹配一种组合完成恢复选择状态(可能其他组合需要使用改坐标完成匹配)
visited[x][y] = false;
return _result;
}
// 上面逻辑为查找到满足条件的组合,返回false
return false
};