1
class TrieNode {
2
 public:
3
  bool isEnd;
4
  vector<TrieNode *> children;
5
  TrieNode() {
6
    isEnd = false;
7
    children = vector<TrieNode *>(26, NULL);
8
  }
9
};
10

11
class Trie {
12
 public:
13
  TrieNode *root;
14
  Trie() {
15
    root = new TrieNode();
16
  }
17

18
  void insert(string &word, bool &isSuffix) {
19
    auto cur = root;
20
    for (int i = 0; i < word.size(); i++) {
21
      int index = word[i] - 'a';
22

23
      // If new node is needed to be inserted for this word, then this word
24
      // can't be suffix of some other word.
25
      if (cur->children[index] == NULL) {
26
        isSuffix = false;
27
        cur->children[index] = new TrieNode();
28
      }
29
      cur = cur->children[index];
30
    }
31
    cur->isEnd = true;
32
  }
33
};
34

35
class Solution {
36
 public:
37
  int minimumLengthEncoding(vector<string> &words) {
38
    sort(words.begin(), words.end(), [](string &a, string &b) { return a.size() > b.size(); });
39

40
    int res = 0;
41
    Trie *trie = new Trie();
42

43
    for (auto word : words) {
44
      reverse(word.begin(), word.end());
45
      bool wordIsSuffix = true;
46
      trie->insert(word, wordIsSuffix);
47
      // If word is not suffix of some other word, it needs to be added
48
      // separately
49
      if (!wordIsSuffix) res += word.size() + 1; //+1 for '#'
50
    }
51
    return res;
52
  }
53
};