1
/**
2
 * @param {string[]} words
3
 * @return {number}
4
 */
5
class Trie {
6
  constructor(letter) {
7
    this.letter = letter;
8
    this.children = new Map();
9
    this.isWord = false;
10
  }
11
}
12

13
var minimumLengthEncoding = function (words) {
14
  let minEncodingLength = 0;
15
  const sortedWords = words.sort((a, b) => a.length - b.length);
16

17
  const buildTrie = (root, word, index) => {
18
    // This means we reached to the end of word, so mark it as a word and compute encoding length
19
    if (index < 0) {
20
      minEncodingLength += word.length + 1;
21
      root.isWord = true;
22
      return;
23
    }
24

25
    const character = word[index];
26
    // If we do not have a char in children, create a node and add it under root
27
    if (!root.children.has(character)) {
28
      const node = new Trie(character);
29
      root.children.set(character, node);
30
      buildTrie(node, word, index - 1);
31
      return;
32
    }
33

34
    const node = root.children.get(character);
35
    // Remove the common suffix length considered before since it would be covered as a part of current word traversal
36
    if (node.isWord) {
37
      node.isWord = false;
38
      minEncodingLength -= word.length - index + 1;
39
    }
40

41
    buildTrie(node, word, index - 1);
42
  };
43

44
  const root = new Trie();
45
  for (const word of sortedWords) {
46
    buildTrie(root, word, word.length - 1);
47
  }
48

49
  return minEncodingLength;
50
};