目录
题目来源
题目描述
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中”相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例
输入
board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]],
word = “ABCCED”
输出true说明
输入
board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]],
word = “SEE”
输出true说明
输入
board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]],
word = “ABCB”
输出false说明
提示
- m == board.length
- n = board[i].length
- 1
题目解析
本题逻辑分析起来还是很简单的，就是遍历board矩阵中每一个元素board[i][j]，然后以遍历到的元素board[i][j]为起始点，对比word[0]，如果相同，则继续遍历board[i][j]的上下左右四个方向上的点，若存在某个点board[i][j] === word[]，则继续以board[i][j*]为中心，遍历其上下左右四个方向，需要注意的是四个方向是”或关系”，即一个方向不符合要求，则可以尝试另一个方向，只有四个方向都不符合，才能判定board[i][j]为起点的路径不存在符合题意要求的解，因此我们可以使用回溯算法。
另外，有一个注意点是，如果要求下图是否存在ABAB路径
则我们会发现，A -> B 后，B的四个方向中又包含了访问过的点A，而这是不行的，因此我们需要排除掉访问过的点。
我们可以定义一个和board行列数相同的二维数组visited，初始所有元素值为false，表示当前点未被访问过，如果某点被访问了，则将visited[i][j]赋值为true。依靠visited，我们就可以避免访问到已经访问过的点。
算法源码
/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
/* 此段代码可大幅提示性能，可能是切中了leetcode的用例设计 */
const set = new Set(board.toString().split(',')) // 二维数组扁平化
for(let i=0; i new Array(m).fill(false))
const backTracking = (i, j, k) => {
if(k === len) return true
if(i < 0 || i >= n || j < 0 || j >= m || visited[i][j] || board[i][j] != word[k]) return false
visited[i][j] = true
const newK = k + 1
const res =
backTracking(i-1, j, newK) ||
backTracking(i+1, j, newK) ||
backTracking(i, j-1, newK) ||
backTracking(i, j+1, newK)
visited[i][j] = false
return res
}
for(let i=0; i
Original: https://blog.csdn.net/qfc_128220/article/details/127820957
Author: 伏城之外
Title: LeetCode – 79 单词搜索
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/659516/
转载文章受原作者版权保护。转载请注明原作者出处！