leetcode

0 class Trie {

1 struct Node {

2 Node(){};

3 Node *children[27] = {nullptr};

4 bool &terminate = reinterpret_cast<bool &>(children[0]);

5 };

6

7 Node *trie = new Node();

8

9 int length_rec(const Node *node, int len = 0) const {

10 int res = 1, had = 0;

11 for (int i = 1; i <= 26; i++) {

12 if (!node->children[i]) continue;

13 if (had) res += len + 1;

14 res += length_rec(node->children[i], len + 1);

15 had = true;

16 }

17 return res;

18 }

19

20 public:

21 void insert(const string &s) {

22 Node *crnt = trie;

23 for (int i = s.size() - 1; i >= 0; i--) {

24 const int idx = s[i] & 0x1F;

25 if (!crnt->children[idx]) crnt->children[idx] = new Node();

26 crnt = crnt->children[idx];

27 }

28 crnt->terminate = true;

29 }

30

31 int length(void) const { return length_rec(trie); }

32 };

33

34 class Solution {

35 public:

36 int minimumLengthEncoding(const vector<string> &words) {

37 Trie trie;

38 for (const string &word : words)

39 trie.insert(word);

40 return trie.length();

41 }

42 };