79. 单词搜索

描述

给定一个 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 仅由大小写英文字母组成
复制代码

题解

不同于排列组合修改输出方式，而是修改访问标记。

在我们对任意位置进行深度优先搜索时，我们先标记当前位置为已访问，以避免重复遍历（如防止向右搜索后
又向左返回);

在所有的可能都搜索完成后，再回改当前位置为未访问，防止干扰其它位置搜索
到当前位置。

使用回溯法，我们可以只对一个二维的访问矩阵进行修改，而不用把每次的搜索状
态作为一个新对象传入递归函数中。

coding

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
const direction = [-1, 0, 1, 0, -1];
const exist = function(board, word) {
   if(!board.length) return false;
   let m = board.length, n = board[0].length;
   let visited = Array.from({length: m}, ()=> Array(n).fill(false));
   const find = {flag:false};
   for(let i = 0; i < m; i++) {
       for(let j = 0; j < n; j++) {
            backtracking(i, j, board, word, find, visited, 0);
       }
   }
   return find.flag;
};
const backtracking = function(i, j, board, word, find,visited, pos) {
    if(i < 0 || i >= board.length || j < 0 || j >= board[0].length) {
        return;
    } 
    if(visited[i][j] || (board[i][j] !== word[pos]) || find.flag) {
        return;
    }
    if(pos === word.length - 1) {
      find.flag = true
      return;
    }
    visited[i][j] = true; // 修改当前节点状态。
     for(let k = 0; k < 4; k++){
         const dx = i + direction[k];
         const dy = j + direction[k+1];
         backtracking(dx, dy, board, word,find, visited, pos + 1);
     }
     visited[i][j] = false; // 恢复节点状态；

}

复制代码