C++ Solution || Trie
Intuition\nThe problem is about calculating a score for each word based on how many times its prefixes appear across all the words in the input list. A Trie (pr
# Intuition\nThe problem is about calculating a score for each word based on how many times its prefixes appear across all the words in the input list. A Trie (prefix tree) is an efficient data structure for handling prefix-based problems because it allows for fast insertion and traversal of strings. By storing prefix frequencies in the Trie, we can quickly calculate the prefix score for each word.\n\n# Approach\n1. Use a Trie data structure where each node represents a character and contains a `countP` value, which keeps track of how many times this character (or its associated prefix) has been encountered.\n2. Insert each word into the Trie, incrementing the `countP` value at each character node as you traverse through the word.\n3. For each word, traverse the Trie and accumulate the `countP` values to calculate the prefix score.\n4. Return a list of prefix scores, where each score corresponds to a word in the input list.\n\n# Complexity\n- Time complexity: $$O(n*w)$$\n\n- Space complexity: $$O(n*w)$$\n\n# Code\n```cpp []\nstruct trie {\n    int countP = 0;\n    trie* children[26];\n};\n\nclass Solution {\npublic:\n    trie* getTrieNode() {\n        trie* newNode = new trie();\n        for (int i = 0; i < 26; i++) {\n            newNode->children[i] = NULL;\n        }\n        newNode->countP = 0;\n        return newNode;\n    }\n\n    void insert(string& word, trie* root) {\n        trie* node = root;\n        for (auto ch : word) {\n            int ind = ch - \'a\';\n\n            if (node->children[ind] == NULL) {\n                node->children[ind] = getTrieNode();\n            }\n            node->children[ind]->countP += 1;\n            node = node->children[ind];\n        }\n    }\n\n    int getScore(string& word, trie* root) {\n        trie* node = root;\n        int score = 0;\n        for (auto ch : word) {\n            int ind = ch - \'a\';\n            score += node->children[ind]->countP;\n            node = node->children[ind];\n        }\n        return score;\n    }\n\n    vector<int> sumPrefixScores(vector<string>& words) {\n        int n = words.size();\n        trie* root = getTrieNode();\n        for (auto& word : words) {\n            insert(word, root);\n        }\n\n        vector<int> res(n);  \n\n        for (int i = 0; i < n; i++) {\n            res[i] = getScore(words[i], root);\n        }\n\n        return res;\n    }\n};\n\n```\n> *In coding, as in life, it\u2019s all about the connections\u2014Tries are just really good at finding the right ones!*\n\n![1721315779911.jpeg](https://assets.leetcode.com/users/images/7012b39a-1e50-46df-ac6d-94532de798aa_1727245992.2560966.jpeg)\n\n
['String', 'Trie', 'C++']