1
const buildTrie = (words) => {
2
  const trie = {};
3
  const addToTrie = (word, index = 0, node = trie) => {
4
    const char = word[index];
5
    if (!node[char]) {
6
      node[char] = {};
7
    }
8

9
    if (index === word.length - 1) {
10
      node[char].word = word;
11
      return word;
12
    }
13

14
    return addToTrie(word, index + 1, node[char]);
15
  };
16

17
  words.map((word) => addToTrie(word));
18
  return trie;
19
};
20

21
const dfs = (i, j, board, node, wordsFound = []) => {
22
  if (i < 0 || i >= board.length) return wordsFound;
23
  if (j < 0 || j >= board[board.length - 1].length) return wordsFound;
24

25
  const char = board[i][j];
26
  if (char === "#") return wordsFound;
27

28
  if (node[char]) {
29
    if (node[char].word) {
30
      wordsFound.push(node[char].word);
31
      node[char].word = null;
32
    }
33

34
    board[i][j] = "#";
35
    dfs(i + 1, j, board, node[char], wordsFound);
36
    dfs(i, j + 1, board, node[char], wordsFound);
37
    dfs(i - 1, j, board, node[char], wordsFound);
38
    dfs(i, j - 1, board, node[char], wordsFound);
39
    board[i][j] = char;
40
  }
41

42
  return wordsFound;
43
};
44

45
var findWords = function (board, words) {
46
  const m = board.length;
47
  const n = board[m - 1].length;
48
  const trie = buildTrie(words);
49

50
  let result = [];
51
  for (let i = 0; i < m; i += 1) {
52
    for (let j = 0; j < n; j += 1) {
53
      result = result.concat(dfs(i, j, board, trie));
54
    }
55
  }
56
  return result;
57
};