Concatenated Words LeetCode solution in JavaScript

1
class Node {
2
  val;
3
  children;
4
  isWord = false;
5
  constructor(val) {
6
    this.val = val;
7
  }
8
}
9
class Trie {
10
  nodes = Array(26);
11
  addWord(w) {
12
    let idx = this.getIdx(w[0]);
13
    let node = this.nodes[idx] || new Node(w[0]);
14
    this.nodes[idx] = node;
15
    for (let i = 1; i < w.length; ++i) {
16
      node.children = node.children || Array(26);
17
      idx = this.getIdx(w[i]);
18
      let childNode = node.children[idx] || new Node(w[i]);
19
      node.children[idx] = childNode;
20
      node = childNode;
21
    }
22

23
    node.isWord = true;
24
  }
25

26
  getExistingWords(w, start) {
27
    const rslt = [];
28
    let node = { children: this.nodes };
29
    for (let i = start; i < w.length; ++i) {
30
      node = (node.children || [])[this.getIdx(w[i])];
31
      if (!node) {
32
        break;
33
      }
34

35
      if (node.isWord) {
36
        rslt.push(i - start + 1);
37
      }
38
    }
39

40
    return rslt;
41
  }
42

43
  getIdx(ch) {
44
    return ch.charCodeAt(0) - "a".charCodeAt(0);
45
  }
46
}
47

48
var findAllConcatenatedWordsInADict = function (words) {
49
  const rslt = [];
50
  words = words.sort((a, b) => a.length - b.length);
51
  let start = 0;
52
  if (words[0].length === 0) {
53
    ++start;
54
  }
55
  const tr = new Trie();
56
  for (let i = start; i < words.length; ++i) {
57
    if (check(words[i], 0, tr, Array(words[i].length))) {
58
      rslt.push(words[i]);
59
    }
60
    tr.addWord(words[i]);
61
  }
62

63
  return rslt;
64
};
65

66
function check(word, i, trie, dp) {
67
  if (i > word.length || dp[i] === false) {
68
    return false;
69
  }
70
  if (i === word.length || dp[i] === true) {
71
    return true;
72
  }
73
  const lens = trie.getExistingWords(word, i);
74
  if (!lens.length) {
75
    dp[i] = false;
76
    return false;
77
  }
78

79
  dp[i] = true;
80
  for (let l of lens) {
81
    if (check(word, i + l, trie, dp)) {
82
      return true;
83
    }
84
  }
85

86
  dp[i] = false;
87

88
  return false;
89
}