给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。 示例:board =[  ['A','B','C','E'],  ['S','F','C','S'],  ['A','D','E','E']]给定 word = "ABCCED", 返回 true给定 word = "SEE", 返回 true给定 word = "ABCB", 返回 false 提示：board 和 word 中只包含大写和小写英文字母。1 <= board.length <= 2001 <= board[i].length <= 2001 <= word.length <= 10^3

1. 扫描二维数组，找到board[1,0] = word[0]，匹配单词首字母。2. 做DFS（上，下，左，右 四个方向）如下图：

1. 标记当前字符（1，0）为已经访问过，board[1][0] = '*'2. 上（0，0）字符为 'A' 不匹配,3. 下（2，0）字符为 'A'，不匹配,4. 左（-1，0）超越边界，不匹配,5. 右（1，1）字符 'F'，不匹配如下图：

1. 回溯，标记起始位置（1，0）为未访问。board[1][0] = 'S'.2. 然后继续扫描二维数组，找到下一个起始位置（1，3）如下图：

1. 标记当前字符（1, 3）为已经访问过，board[1][3] = '*'2. 上（0，3）字符为 'E', 匹配, 继续DFS搜索（参考位置为（0，3）位置DFS搜索步骤描述）3. 下（2，3）字符为 'E'，匹配, #2匹配，先进行#2 DFS搜索，由于#2 DFS搜索没有找到与单词匹配，继续DFS搜索（参考位置为（2，3）DFS搜索步骤描述）4. 左（1，2）字符为 'C'，不匹配,5. 右（1，4）超越边界，不匹配如下图：

1. 标记当前字符（0，3）为已经访问过，board[0][3] = '*'2. 上 （-1，3）超越边界，不匹配3. 下（1，3）已经访问过，4. 左（0，2）字符为 'C'，不匹配5. 右（1，4）超越边界，不匹配如下图

1. 回溯，标记起始位置（0，3）为未访问。board[0][3] = 'E'.2. 回到满足条件的位置（2，3），继续DFS搜索，判断相邻的字符是否匹配单词下一个字符 'E'3. 上 (1，3）已访问过4. 下（3，3）超越边界，不匹配5. 左（2，2）字符为 'E'，匹配6. 右（2，4）超越边界，不匹配如下图：

public class LC79WordSearch {  public boolean exist(char[][] board, String word) {    if (board == null || word == null) return false;    if (word.length() == 0) return true;    if (board.length == 0) return false;    int rows = board.length;    int cols = board[0].length;    for (int r = 0; r < rows; r++) {      for (int c = 0; c < cols; c++) {        // scan board, start with word first character        if (board[r][c] == word.charAt(0)) {          if (helper(board, word, r, c, 0)) {            return true;          }        }      }    }    return false;  }  private boolean helper(char[][] board, String word, int r, int c, int start) {    // already match word all characters, return true    if (start == word.length()) return true;    if (!isValid(board, r, c) ||        board[r][c] != word.charAt(start)) return false;    // mark visited    board[r][c] = '*';    boolean res = helper(board, word, r - 1, c, start + 1) // 上        ||  helper(board, word, r + 1, c, start + 1)       // 下        ||  helper(board, word, r, c - 1, start + 1)       // 左        ||  helper(board, word, r, c + 1, start + 1);      // 右    // backtracking to start position    board[r][c] = word.charAt(start);    return res;  }  private boolean isValid(char[][] board, int r, int c) {    return r >= 0 && r < board.length && c >= 0 && c < board[0].length;  }}

class Solution:    def exist(self, board: List[List[str]], word: str) -> bool:        m = len(board)        n = len(board[0])        def dfs(board, r, c, word, index):            if index == len(word):                return True            if r < 0 or r >= m or c < 0 or c >= n or board[r][c] != word[index]:                return False            board[r][c] = '*'            res = dfs(board, r - 1, c, word, index + 1) or dfs(board, r + 1, c, word, index + 1) or dfs(board, r, c - 1, word, index + 1) or dfs(board, r, c + 1, word, index + 1)            board[r][c] = word[index]            return res        for r in range(m):            for c in range(n):                if board[r][c] == word[0]:                    if dfs(board, r, c, word, 0):                        return True        return False

/* * @lc app=leetcode id=79 lang=javascript * * [79] Word Search */function DFS(board, row, col, rows, cols, word, cur) {  // 边界检查  if (row >= rows || row < 0) return false;  if (col >= cols || col < 0) return false;  const item = board[row][col];  if (item !== word[cur]) return false;  if (cur + 1 === word.length) return true;  // 如果你用hashmap记录访问的字母， 那么你需要每次backtrack的时候手动清除hashmap，并且需要额外的空间  // 这里我们使用一个little trick  board[row][col] = null;  // 上下左右  const res =    DFS(board, row + 1, col, rows, cols, word, cur + 1) ||    DFS(board, row - 1, col, rows, cols, word, cur + 1) ||    DFS(board, row, col - 1, rows, cols, word, cur + 1) ||    DFS(board, row, col + 1, rows, cols, word, cur + 1);  board[row][col] = item;  return res;}/** * @param {character[][]} board * @param {string} word * @return {boolean} */var exist = function (board, word) {  if (word.length === 0) return true;  if (board.length === 0) return false;  const rows = board.length;  const cols = board[0].length;  for (let i = 0; i < rows; i++) {    for (let j = 0; j < cols; j++) {      const hit = DFS(board, i, j, rows, cols, word, 0);      if (hit) return true;    }  }  return false;};