单词搜索

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

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

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

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

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

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  let n = board.length,
    m = board[0].length;

  function dfs(i, j, word) {
    if (!word) return true;
    if (i < 0 || i >= n || j < 0 || j >= m) return false;
    let char = word[0];
    let next = word.slice(1);
    if (board[i][j] !== char) return false;
    board[i][j] = undefined;
    let res = dfs(i - 1, j, next) || dfs(i + 1, j, next) || dfs(i, j + 1, next) || dfs(i, j - 1, next);
    board[i][j] = char;
    return res;
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (dfs(i, j, word)) return true;
    }
  }
  return false;
};

单词搜索 ​

单词搜索