leetcode

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

0648.cpp (1134B)

      1 class Solution {
      2     struct Node {
      3         Node(){};
      4         Node *children[27] = {nullptr};
      5         bool &terminate = reinterpret_cast<bool &>(children[0]);
      6     };
      7 
      8   public:
      9     string replaceWords(const vector<string> &dictionary, const string &sentence) {
     10         Node *trie = new Node();
     11         for (const string &s : dictionary) {
     12             Node *crnt = trie;
     13             for (const char c : s) {
     14                 const int idx = c & 0x1F;
     15                 if (!crnt->children[idx]) crnt->children[idx] = new Node();
     16                 crnt = crnt->children[idx];
     17             }
     18             crnt->terminate = true;
     19         }
     20 
     21         string res, word, tmp;
     22         stringstream ss(sentence);
     23         while (ss >> word) {
     24             Node *crnt = trie;
     25             for (const char c : word) {
     26                 const int idx = c & 0x1F;
     27                 if (!crnt->children[idx] || crnt->terminate) break;
     28                 crnt = crnt->children[idx];
     29                 tmp += c;
     30             }
     31             res += (crnt->terminate ? tmp : word) + ' ';
     32             tmp.clear();
     33         }
     34         res.pop_back();
     35         return res;
     36     }
     37 };