单词搜索

[Cosen95]

leetcode: https://leetcode-cn.com/problems/word-search/

[Cosen95]

题目难度medium，涉及到的算法知识有DFS和回溯。

题目描述

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

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

示例：

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) {
    // if (board.length === 0) return false;
    // if (word.length === 0) return true;
    const row = board.length;
    const col = board[0].length;
    const visited = new Array(row)
    for(let i=0; i < row; i++) {
        visited[i] = new Array(col)
    }
    for(let i = 0; i < row; i++) {
        for (let j = 0; j < col; j++) {
            if(board[i][j] == word[0] && find(i,j,0)) {    // 找到dfs的起点，并且结果也为true，则找到了目标路径
                return true;
            } 
        }
    }
    return false;   // 默认返回false
    function find(i, j, cur) {
        if(cur > word.length - 1) return true;    // 递归的出口

        if(i >= row || i < 0 || j >=col || j < 0) return false; // 当前点不存在
        if(visited[i][j] || board[i][j] != word[cur]) {    // 当前点已经走过或者当前点不是目标节点
            return false
        }
        visited[i][j] = true    // 到这里表明当前点没有问题，可以继续递归往下走，同时需记录一下当前节点已被访问到
        const res = find(i+1,j,cur+1) ||
                    find(i-1,j,cur+1) ||
                    find(i,j+1,cur+1) ||
                    find(i,j-1,cur+1);
        if (res) return true
        visited[i][j] = false;  // 基于当前节点找不到后面的节点，则继续观察其他分支，并撤销当前节点的访问状态
        return false
    }
};