Word Search II

Solutions

Trie and Depth-First Search

Time: O(N * M * 4^L)Space: O(N * M + L)

The solution uses a Trie data structure to store the words and then uses depth-first search to find all words in the board. The Trie is constructed by iterating over each word and adding each character to the Trie. Then, for each cell in the board, we start a depth-first search from that cell and explore all possible words that can be formed from that cell. If a word is found, it is added to the result list and the word is removed from the Trie to avoid duplicates.

const findWords = (board, words) => {
  const res = [],
    trie = {};
  for (const word of words) {
    let node = trie;

    for (const char of word) {
      if (!node[char]) node[char] = {};

      node = node[char];
    }

    node.end = word;
  }

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

  const dfs = (i, j, node) => {
    if (node.end) {
      res.push(node.end);

      node.end = null;
    }

    if (
      i < 0 ||
      i >= board.length ||
      j < 0 ||
      j >= board[0].length ||
      !node[board[i][j]]
    )
      return;

    const temp = board[i][j];

    board[i][j] = '#';

    for (const [dx, dy] of directions) dfs(i + dx, j + dy, node[board[i][j]]);

    board[i][j] = temp;
  };
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[0].length; j++) {
      dfs(i, j, trie);
    }
  }

  return res;
};

Constraints:

Examples:

Solutions

Trie and Depth-First Search

Follow-up: