LeetCode - 79 单词搜索

目录

题目来源

题目描述

示例

提示

题目解析

算法源码

---

题目来源

79. 单词搜索 - 力扣（LeetCode）

题目描述

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例

 

 

提示

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

题目解析

本题逻辑分析起来还是很简单的，就是遍历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; ilength; i++) {
        if(!set.has(word[i])) return false // 如果word中的字符在board中未出现，则直接返回false
    }
 
    // 以下代码是通用逻辑
    const n = board.length
    const m = board[0].length
    const len = word.length
 
    const visited = new Array(n).fill(0).map(() => 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
        for(let j=0; j
            if(backTracking(i, j, 0)) return true
        }
    }
 
    return false
};