leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0820.cpp (1125B)

      1 class Trie {
      2     struct Node {
      3         Node(){};
      4         Node *children[27] = {nullptr};
      5         bool &terminate = reinterpret_cast<bool &>(children[0]);
      6     };
      7 
      8     Node *trie = new Node();
      9 
     10     int length_rec(const Node *node, int len = 0) const {
     11         int res = 1, had = 0;
     12         for (int i = 1; i <= 26; i++) {
     13             if (!node->children[i]) continue;
     14             if (had) res += len + 1;
     15             res += length_rec(node->children[i], len + 1);
     16             had = true;
     17         }
     18         return res;
     19     }
     20 
     21   public:
     22     void insert(const string &s) {
     23         Node *crnt = trie;
     24         for (int i = s.size() - 1; i >= 0; i--) {
     25             const int idx = s[i] & 0x1F;
     26             if (!crnt->children[idx]) crnt->children[idx] = new Node();
     27             crnt = crnt->children[idx];
     28         }
     29         crnt->terminate = true;
     30     }
     31 
     32     int length(void) const { return length_rec(trie); }
     33 };
     34 
     35 class Solution {
     36   public:
     37     int minimumLengthEncoding(const vector<string> &words) {
     38         Trie trie;
     39         for (const string &word : words)
     40             trie.insert(word);
     41         return trie.length();
     42     }
     43 };