C++ || Easy Tries Implementation ✅✅ || Beats 82.29%
Intuition\nThe problem requires calculating prefix scores for a list of words. The prefix score of a word is defined as the sum of the counts of occurrences of 
# Intuition\nThe problem requires calculating prefix scores for a list of words. The prefix score of a word is defined as the sum of the counts of occurrences of all its prefixes in a trie structure. The trie allows efficient insertion and retrieval of prefix counts, making it a suitable data structure for this task.\n\n# Approach\n1. **Trie Structure**: Create a `Trie` class with a nested `node` class. Each node will store:\n   - `ew`: The count of words that end at that node.\n   - `cp`: The count of prefixes that pass through that node.\n   - An array of pointers to the next nodes corresponding to each character.\n\n2. **Insert Method**: For each word, iterate through its characters:\n   - If the corresponding child node doesn\'t exist, create it.\n   - Move to the child node and update the `cp` count to reflect the number of prefixes that pass through that node.\n   - After processing the word, increment the `ew` count for the last node.\n\n3. **Prefix Count Method**: For each word, calculate the prefix score by iterating through its characters and summing the `cp` counts of the nodes corresponding to each prefix.\n\n4. **Main Function**: For the given list of words, first insert all words into the trie, then calculate the prefix scores for each word and store them in a result vector.\n\n# Complexity\n- **Time complexity**: *O(m.n)*.\n  \n- **Space complexity**: *O(m.n).*\n\n# Code\n```cpp\n#include <string>\n#include <vector>\n\nclass Solution {\n    class Trie {\n        class node {\n            public:\n                int ew, cp;\n                node* next[26];\n                node() {\n                    ew = 0;\n                    cp = 0;\n                    for (int i = 0; i < 26; i++) {\n                        next[i] = nullptr;\n                    }\n                }\n        };\n\n        node *trie;\n\n        public:\n            Trie() {\n                trie = new node();\n            }\n\n            void insert(const string& word) {\n                node *it = trie;\n                for (char ch : word) {\n                    if (it->next[ch - \'a\'] == nullptr) {\n                        it->next[ch - \'a\'] = new node();\n                    }\n                    it = it->next[ch - \'a\'];\n                    it->cp++;\n                }\n                it->ew++;\n            }\n\n            int getPrefCount(const string& word) {\n                node *it = trie;\n                int cnt = 0;\n                for (char ch : word) {\n                    if (it->next[ch - \'a\'] == nullptr) {\n                        return 0;\n                    }\n                    it = it->next[ch - \'a\'];\n                    cnt += it->cp;\n                }\n                return cnt;\n            }\n    };\n\npublic:\n    vector<int> sumPrefixScores(vector<string>& words) {\n        Trie t;\n        for (const auto& word : words) {\n            t.insert(word);\n        }\n        vector<int> ans(words.size(), 0);\n        for (int i = 0; i < words.size(); i++) {\n            ans[i] = t.getPrefCount(words[i]);\n        }\n        return ans;\n    }\n};\n
['String', 'Trie', 'C++']