【Leetcode 346/700】79. 单词搜寻 【中等】 回溯深度搜寻JavaScript版

1.题目

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

单词必须依照字母程序，通过相邻的单元格内的字母形成，其中“相邻”单元格是那些程度相邻或垂直相邻的单元格。同一个单元格内的字母不容许被重复使用。

示例 1：

输出：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"输入：true

示例 2：

输出：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"输入：true

示例 3：

输出：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"输入：false

提醒：

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

2解题思路

1.遍历 board 所有元素，找到 word的第一个雷同的元素，并且进行标记 （marked）,进入递归去找接下来的第二个字符，接着第三个字母。如果没找到，返回 false;

  1. 在设定的边界内进行回溯搜寻，即上下左右进行搜寻下一个字符。找到了进入新的递归，没有找到的话，间接返回false;

3.解题留神点

1.及时进行标记字符的状态，是曾经拜访了，还是未拜访；
2.如果最初所有的字符串截取完了，阐明曾经找到合乎的答案啦，间接返回true;

4.解题代码

/** * @param {character[][]} board * @param {string} word * @return {boolean} */var exist = function (board, word) {    let border = [[0, 1], [0, -1], [1, 0], [-1, 0]], //定义上下左右四个方向        col = board.length, //行数        row = board[0].length, //列数        marked = [...Array(col)].map(v => Array(row).fill()); //同行列空矩阵，用于记录曾经拜访的        //空数组间接返回false    if (!col) return false;    let backTracing = (i, j, markeds, boards, words) => {        //截取所有的字符，阐明曾经找到        if (!words.length) {            return true;        }        for (let p = 0; p < border.length; p++) {            let curi = i + border[p][0]; //左右方向            let curj = j + border[p][1]; //高低方向            //判断边界，且找到了第一个字符            if ((curi >= 0 && curi < col) && (curj >= 0 && curj < row && boards[curi][curj] == words[0])) {                //曾经用过，间接跳过                if (markeds[curi][curj] == 1) {                    continue                }                //标记为已应用                markeds[curi][curj] = 1;                //接着找下一个字符                if (backTracing(curi, curj, markeds, boards, words.substring(1))) {                    return true                } else {                    //应用完重置掉                    markeds[curi][curj] = 0;                }            }        }        return false    }    for (let i = 0; i < col; i++) {        for (let j = 0; j < row; j++) {            if (board[i][j] === word[0]) {                //找到第一个字符，标记为曾经应用                marked[i][j] = 1;                //进入回溯                if (backTracing(i, j, marked, board, word.substring(1))) {                    return true                } else {                    //重置状态                    marked[i][j] = 0;                }            }        }    }    return false};//测试用例 1let board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word = "ABCCED";//测试用例2let board1 = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word1 = "SEE"//测试用例3let board2 = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word2 = "ABCB"console.log(exist(board, word))  //trueconsole.log(exist(board1, word1)) //trueconsole.log(exist(board2, word2)) //false