Skip to main content

79. Word Search

分析


题解

/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function (board, word) {
const m = board.length
const n = board[0].length
let ans = false

const dirs = [
[-1, 0],
[0, 1],
[1, 0],
[0, -1],
]

const visited = Array.from({ length: m }, () => new Array(n).fill(false))

const canUse = (x, y, index) => {
const inBoard = x >= 0 && x < m && y >= 0 && y < n
return inBoard && !visited[x][y] && word[index] === board[x][y]
}

const dfs = (x, y, index) => {
// 检验
if (!canUse(x, y, index)) {
return
}
visited[x][y] = true

// 匹配情况
if (index === word.length - 1) {
ans = true
visited[x][y] = false
return
}

for (let i = 0; i < dirs.length; i++) {
const nextX = x + dirs[i][0]
const nextY = y + dirs[i][1]
dfs(nextX, nextY, index + 1)
}
visited[x][y] = false
}

for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
dfs(i, j, 0)
}
}

return ans
}