1
function TrieNode(key) {
2
  this.key = key;
3
  this.parent = null;
4
  this.children = {};
5
  this.end = false;
6

7
  this.getWord = function () {
8
    let output = [];
9
    let node = this;
10

11
    while (node !== null) {
12
      output.unshift(node.key);
13
      node = node.parent;
14
    }
15

16
    return output.join("");
17
  };
18
}
19

20
function Trie() {
21
  this.root = new TrieNode(null);
22

23
  this.insert = function (word) {
24
    let node = this.root;
25

26
    for (let i = 0; i < word.length; i++) {
27
      if (!node.children[word[i]]) {
28
        node.children[word[i]] = new TrieNode(word[i]);
29
        node.children[word[i]].parent = node;
30
      }
31

32
      node = node.children[word[i]];
33

34
      if (i === word.length - 1) {
35
        node.end = true;
36
      }
37
    }
38
  };
39

40
  this.findAllWords = function (node, arr) {
41
    if (node.end) {
42
      arr.unshift(node.getWord());
43
    }
44

45
    for (let child in node.children) {
46
      this.findAllWords(node.children[child], arr);
47
    }
48
  };
49

50
  this.find = function (prefix) {
51
    let node = this.root;
52
    let output = [];
53

54
    for (let i = 0; i < prefix.length; i++) {
55
      if (node.children[prefix[i]]) {
56
        node = node.children[prefix[i]];
57
      } else {
58
        return output;
59
      }
60
    }
61

62
    this.findAllWords(node, output);
63

64
    output.sort();
65

66
    return output.slice(0, 3);
67
  };
68

69
  this.search = function (word) {
70
    let node = this.root;
71
    let output = [];
72

73
    for (let i = 0; i < word.length; i++) {
74
      output.push(this.find(word.substring(0, i + 1)));
75
    }
76

77
    return output;
78
  };
79
}
80

81
/**
82
 * @param {string[]} products
83
 * @param {string} searchWord
84
 * @return {string[][]}
85
 */
86
var suggestedProducts = function (products, searchWord) {
87
  let trie = new Trie();
88

89
  for (let product of products) {
90
    trie.insert(product);
91
  }
92

93
  return trie.search(searchWord);
94
};