leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0820.cpp (1125B)

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 };