79. Word Search

https://leetcode.com/problems/word-search/

Python

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        row_limit = len(board)
        col_limit = len(board[0])

        used = set()

        def backtrack(row, col, index):
            if index == len(word):
                return True

            if board[row][col] != word[index]:
                return False

            up = down = right = left = False
            used.add((row, col))

            next_index = index + 1
            if row - 1 >= 0 and (row-1, col) not in used:
                up = backtrack(row-1, col, next_index)

            if row + 1 < row_limit and (row+1, col) not in used:
                down = backtrack(row+1, col, next_index)

            if col - 1 >= 0 and (row, col-1) not in used:
                left = backtrack(row, col-1, next_index)

            if col + 1 < col_limit and (row, col+1) not in used:
                right = backtrack(row, col+1, next_index)

            used.remove((row, col))
            # print(row, col, board[row][col], up, down, left, right, used)
            return up or down or right or left or index == len(word)-1

        for row in range(row_limit):
            for col in range(col_limit):
                if backtrack(row, col, 0):
                    return True
        return False

Javascript

var exist = function (board, word) {
  const finding = new Finding(board, word);

  for (let row = 0; row < board.length; row++) {
    for (let col = 0; col < board[row].length; col++) {
      if (finding.track(row, col)) return true;
    }
  }
  return false;
};

class Finding {
  constructor(board, word) {
    this.maxRows = board.length;
    this.maxCols = board[0].length;
    this.board = board;
    this.word = word;
  }

  track(row, col, i = 0) {
    // matched
    if (i >= this.word.length) return true;

    if (row < 0 || row >= this.maxRows || col < 0 || col >= this.maxCols || this.word[i] !== this.board[row][col]) {
      return;
    }
    // console.log([row, col], i, this.word[i])

    let res = false;
    this.board[row][col] = null;
    // console.log(this.board)

    const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    for (const [x, y] of directions) {
      res = this.track(row + y, col + x, i + 1);
      if (res) break;
    }
    // console.log([row, col], this.word[i])
    this.board[row][col] = this.word[i]

    return res;
  }
}