C++ | Trie | Related Problems
Store each string in trie and add 1 to each prefix of string while inserting.\n- Then, for each string, we sum up the count for all its prefixes.\n\n\n\ncpp\nst
- Store each string in trie and **add 1 to each prefix of string while inserting**.\n- Then, for each string, **we sum up the count for all its prefixes**.\n![image](https://assets.leetcode.com/users/images/fde5fc03-7578-4e5f-91e4-570837f1057a_1663474247.6931121.png)\n\n\n```cpp\nstruct TrieNode {\n    TrieNode *next[26] = {};\n    int cnt = 0;\n};\n\nclass Solution {\n    TrieNode root;\npublic:\n    void insert(string word) {\n        auto node = &root;\n        for(char c : word) {\n            if(!node->next[c - \'a\']) {\n                node->next[c - \'a\'] = new TrieNode();\n            } \n            node->next[c - \'a\']->cnt++;\n            node = node->next[c - \'a\'];   \n        }\n    }\n\n    int prefixCnt(string s) {\n        auto node = &root;\n        int ans = 0;\n        for(char c : s) {\n            ans += node->next[c - \'a\']->cnt;\n            node = node->next[c - \'a\'];\n        }\n        return ans;\n    }\n    \n    vector<int> sumPrefixScores(vector<string>& words) {\n        int N = words.size();\n\t\t// Insert words in trie.\n        for (int i = 0; i < N; i++) {\n                insert(words[i]);\n        }\n        vector<int> ans(N, 0);\n        for (int i = 0; i < N; i++) {\n\t\t\t// Get the count of all prefixes of given string.\n            ans[i] = prefixCnt(words[i]); \n        }\n        return ans;\n    }\n};\n```\n\n**Trie Related Problems**\n[1. Implement Trie (Prefix Tree) ](https://leetcode.com/problems/implement-trie-prefix-tree/)\n[2. Palindrome Pairs ](https://leetcode.com/problems/palindrome-pairs/)\n[3. Maximum XOR of Two Numbers in an Array ](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/)\n[4. Concatenated Words ](https://leetcode.com/problems/concatenated-words/)\n[5. Search Suggestions System ](https://leetcode.com/problems/search-suggestions-system/)\n
['Trie', 'C']