leetcode-79 单词搜索

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  const m = board.length;
  const n = board[0].length;
  let res = false;
  // 构造访问数组
  const visited = Array.from({ length: m }, () =>
    Array.from({ length: n }, () => false)
  );
  function backtrack(path, cur, row, col) {
    if (path[cur] !== word[cur]) {
      return;
    }
    if (path === word) {
      res = true;
      return;
    }
    if (path.length > word.length) {
      return;
    }
    // 上下左右四个方向
    // 上 board[row-1][col]
    // 下 board[row+1][col]
    // 左 board[row][col-1]
    // 右 board[row][col+1]
    if (row - 1 >= 0 && !visited[row - 1][col]) {
      visited[row - 1][col] = true;
      backtrack(path + board[row - 1][col], cur + 1, row - 1, col);
      visited[row - 1][col] = false;
    }
    if (row + 1 < m && !visited[row + 1][col]) {
      visited[row + 1][col] = true;
      backtrack(path + board[row + 1][col], cur + 1, row + 1, col);
      visited[row + 1][col] = false;
    }
    if (col - 1 >= 0 && !visited[row][col - 1]) {
      visited[row][col - 1] = true;
      backtrack(path + board[row][col - 1], cur + 1, row, col - 1);
      visited[row][col - 1] = false;
    }
    if (col + 1 < n && !visited[row][col + 1]) {
      visited[row][col + 1] = true;
      backtrack(path + board[row][col + 1], cur + 1, row, col + 1);
      visited[row][col + 1] = false;
    }
  }
  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      visited[row][col] = true;
      backtrack(board[row][col], 0, row, col);
      visited[row][col] = false;
    }
  }
  return res;
};
console.log(
  exist(
    [
      ["A", "B", "C", "E"],
      ["S", "F", "C", "S"],
      ["A", "D", "E", "E"],
    ],
    "ABCCED"
  )
);

/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  const m = board.length;
  const n = board[0].length;
  // 构造访问数组
  const visited = Array.from({ length: m }, () =>
    Array.from({ length: n }, () => false)
  );
  const dirs = [
    [-1, 0], // 上
    [1, 0], // 下
    [0, -1], // 左
    [0, 1], // 右
  ];
  function backtrack(row, col, cur) {
    // 已经被用过
    if (board[row][col] !== word[cur]) return false;
    if (cur === word.length - 1) return true;
    visited[row][col] = true;
    for (const [dx, dy] of dirs) {
      const newRow = row + dx;
      const newCol = col + dy;
      if (
        newRow >= 0 &&
        newRow < m &&
        newCol >= 0 &&
        newCol < n &&
        !visited[newRow][newCol]
      ) {
        if (backtrack(newRow, newCol, cur + 1)) {
          return true;
        }
      }
    }
    visited[row][col] = false;
    return false;
  }
  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      if (backtrack(row, col, 0)) return true;
    }
  }
  return false;
};
// console.log(
//   exist(
//     [
//       ["A", "B", "C", "E"],
//       ["S", "F", "C", "S"],
//       ["A", "D", "E", "E"],
//     ],
//     "ABCCED"
//   )
// );