limanting 的个人博客

题目

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

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

例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的答案

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
    var i = 0, j = 0;
    var pathTag = [];
    for (let p = 0; p < board.length; p++) {
        pathTag[p] = [];
    }
    while (i < board.length && j < board[0].length) {
        if (hasChild(board, word, i, j, 0, pathTag)) {
            return true;
        } else {
            if (j === board[0].length - 1) {
                i++;
                j = 0;
            } else {
                j++;
            }
        }
    }
    return false;
};

var hasChild = function (board, word, x, y, index, pathTag) {
    if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || pathTag[x][y]) {
        return false;
    }
    pathTag[x][y] = true;
    if (board[x][y] === word[index]) {
        if (index === (word.length - 1)) {
            pathTag[x][y] = false;
            return true;
        } else {
            const flag = (hasChild(board, word, x, y + 1, index + 1, pathTag) || hasChild(board, word, x + 1, y, index + 1, pathTag) || hasChild(board, word, x, y - 1, index + 1, pathTag) || hasChild(board, word, x - 1, y, index + 1, pathTag));
                pathTag[x][y] = false;
                return flag;
        }
    } else {
        pathTag[x][y] = false;
        return false;
    }

}

这是一个典型的深搜，但是还要注意给的限制条件（选过的不可以再选）。

深搜就是使用递归就好了，返回条件就是最后一个也匹配到了。

然后说限制条件：选过的不可以再选。这个肯定是需要一个存储和检查的，唯一的点是什么时候把节点设为不可访问。从题目意思可以看出，只要在尝试走的过程中就不能再访问，只有开始返回结果后才能重新允许访问。