leetcode

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

2418.cpp (1128B)

      1 class Solution {
      2     class Trie {
      3         struct Node {
      4             Node *children[26] = {nullptr};
      5             int count = 0;
      6         } node;
      7 
      8       public:
      9         void insert(const string &word) {
     10             Node *crnt = &node;
     11 
     12             for (const char c : word) {
     13                 const auto idx = c - 'a';
     14                 if (!crnt->children[idx]) crnt->children[idx] = new Node();
     15                 crnt = crnt->children[idx];
     16                 crnt->count++;
     17             }
     18         }
     19 
     20         int count(const string &word) const {
     21             const Node *crnt = &node;
     22             int res = 0;
     23 
     24             for (const char c : word) {
     25                 const auto idx = c - 'a';
     26                 crnt = crnt->children[idx];
     27                 res += crnt->count;
     28             }
     29 
     30             return res;
     31         }
     32     };
     33 
     34   public:
     35     vector<int> sumPrefixScores(const vector<string> &words) const {
     36         vector<int> res;
     37         Trie trie;
     38 
     39         for (const auto &word : words)
     40             trie.insert(word);
     41         for (const auto &word : words)
     42             res.push_back(trie.count(word));
     43 
     44         return res;
     45     }
     46 };