212. Word Search II

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

Python

Backtracking (Timelimit Exceed)

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

        length_limit = max([len(word) for word in words])
        used = set()

        accepts = set(words)
        result = set()

        def backtrack(word, row, col):
            word = word + board[row][col]

            if len(word) > length_limit:
                return

            if word in accepts:
                result.add(word)

            used.add((row, col))

            # Go up
            if row - 1 >= 0 and (row-1, col) not in used:
                backtrack(word, row-1, col)

            # Go down
            if row + 1 < row_limit and (row+1, col) not in used:
                backtrack(word, row+1, col)

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

            # Go right
            if col + 1 < col_limit and (row, col+1) not in used:
                backtrack(word, row, col+1)

            used.remove((row, col))

        for row in range(row_limit):
            for col in range(col_limit):
                backtrack('', row, col)
        return result

Javascript

var findWords = function (board, words) {
  const trie = new Trie();
  trie.create(words)
  const trieRoot = trie.get();

	this.finding = new Finding(board);
	return this.finding.findWords(trieRoot);
};

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

	findWords(root) {
    for (let row = 0; row < this.board.length; row++) {
      for (let col = 0; col < this.board[row].length; col++) {
        if (root.childs[this.board[row][col]]) {
          this.find(row, col, root)
        }
      }
    }
    // console.log(this.result)
    return this.result;
	}

	find(row, col, root) {
    const letter = this.board[row][col];
    const currNode = root.childs[letter];

    if (currNode.word) {
      this.result.push(currNode.word)
      currNode.word = '';
    }

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

		const directions = [ [0, 1], [0, -1], [1, 0], [-1, 0] ];

		for (const [x, y] of directions) {
      const nextRow = row + x;
      const nextCol = col + y;

      if ( nextRow >= 0 && nextRow < this.maxRows && nextCol >= 0 && nextCol < this.maxCols) {
        const nextLetter = this.board[nextRow][nextCol];
        // console.log(currNode.childs[nextLetter])
        if (currNode.childs[nextLetter]) {
          this.find(nextRow, nextCol, currNode)
        }
      }
		}

    this.board[row][col] = letter;
	}
}

class TrieNode {
  constructor() {
    this.childs = {};
    this.word = '';
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  create(words) {
    for (const word of words) {
      let node = this.root;
      for (let letter of word) {
        if (node.childs[letter]) {
          node = node.childs[letter];
        } else {
          const newNode = new TrieNode();
          node.childs[letter] = newNode;
          node = newNode;
        }
      }
      node.word = word;
    }
  }

  get() { return this.root; }
}