79. 单词搜索

// 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
// 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
var exist = function(board, word) {
  const column = board.length,
    row = board[0].length;
  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  const enumObj = {};
  const check = (i, j, k) => {
    if (board[i][j] !== word.charAt(k)) return false;
    else if (k === word.length - 1) return true;

    enumObj["" + i + j] = true;
    let result = false;

    for (const [x, y] of directions) {
      const newI = i + x,
        newJ = j + y;
      if (newI >= 0 && newI < column && newJ >= 0 && newJ < row) {
        if (!enumObj["" + newI + newJ]) {
          const flag = check(newI, newJ, k + 1);
          if (flag) {
            result = true;
            break;
          }
        }
      }
    }
    enumObj["" + i + j] = false;
    return result;
  };

  for (let i = 0; i < column; i++) {
    for (let j = 0; j < row; j++) {
      const flag = check(i, j, 0);
      if (flag) {
        return true;
      }
    }
  }

  return false;
};
console.log(
  exist(
    [
      ["A", "B", "C", "E"],
      ["S", "F", "C", "S"],
      ["A", "D", "E", "E"],
    ],
    "ABCCED"
  )
); // true