Trie || Beats 97% || C++ || Python || Java
Intuition\nThe goal of the problem is to calculate the total score of every non-empty prefix of each word in a given list of strings. The score of a prefix is d
# Intuition\nThe goal of the problem is to calculate the total score of every non-empty prefix of each word in a given list of strings. The score of a prefix is defined as the number of strings in the list that start with that prefix.\n\nTo solve this efficiently, we can use a Trie (prefix tree) data structure. The Trie allows us to group words by their prefixes and efficiently count how many words share a given prefix.\n\n# Approach\n1. **Use of Trie**:\n   - Implement a Trie (prefix tree) to efficiently group words by their prefixes.\n\n2. **Building the Trie**:\n   - Iterate through each word in the input list.\n   - For each character in the word, navigate through the Trie.\n   - Create nodes as necessary and maintain a count at each node to track how many words share that prefix.\n\n3. **Calculating Prefix Scores**:\n   - For each word, traverse the Trie again character by character.\n   - Accumulate the counts from the Trie nodes to compute the total score for all non-empty prefixes of that word.\n\n4. **Final Output**:\n   - Return an array where each element corresponds to the total prefix score of the respective word in the input list.\n# Complexity\n- Time complexity:\n$$O(n *m)$$ \n\n- Space complexity:\n$$O(n *m)$$ \n\n# Code\n```python3 []\nclass Solution:\n    def sumPrefixScores(self, words: List[str]) -> List[int]:\n        # Build the trie structure from the list of words\n        trie = self.buildTrie(words)\n        # Calculate and return the prefix scores for each word\n        return self.calculatePrefixScores(trie, words)\n\n    def buildTrie(self, words: List[str]) -> Dict:\n        trie = {}\n        for word in words:\n            node = trie\n            for char in word:\n                # Navigate through or create nodes in the trie\n                node = node.setdefault(char, {})\n                # Count occurrences of the prefix\n                node[\'$\'] = node.get(\'$\', 0) + 1\n        return trie\n\n    def calculatePrefixScores(self, trie: Dict, words: List[str]) -> List[int]:\n        scores = []\n        for word in words:\n            node = trie\n            total_score = 0\n            for char in word:\n                # Move to the next node and accumulate the score\n                node = node[char]\n                total_score += node[\'$\']\n            scores.append(total_score)\n        return scores\n\n```\n``` cpp []\n#include <vector>\n#include <string>\n#include <unordered_map>\n\nclass Solution {\npublic:\n    std::vector<int> sumPrefixScores(std::vector<std::string>& words) {\n        // Build the trie structure from the list of words\n        auto trie = buildTrie(words);\n        // Calculate and return the prefix scores for each word\n        return calculatePrefixScores(trie, words);\n    }\n\nprivate:\n    // Trie node structure\n    struct TrieNode {\n        std::unordered_map<char, TrieNode*> children;\n        int prefixCount = 0;\n    };\n\n    // Build the trie from the words\n    TrieNode* buildTrie(const std::vector<std::string>& words) {\n        TrieNode* root = new TrieNode();\n        for (const std::string& word : words) {\n            TrieNode* node = root;\n            for (char ch : word) {\n                // Navigate through or create nodes in the trie\n                node = node->children[ch];\n                if (!node) {\n                    node = new TrieNode();\n                    node->children[ch] = node;\n                }\n                // Count occurrences of the prefix\n                node->prefixCount++;\n            }\n        }\n        return root;\n    }\n\n    // Calculate prefix scores based on the trie\n    std::vector<int> calculatePrefixScores(TrieNode* trie, const std::vector<std::string>& words) {\n        std::vector<int> scores;\n        for (const std::string& word : words) {\n            TrieNode* node = trie;\n            int totalScore = 0;\n            for (char ch : word) {\n                // Move to the next node and accumulate the score\n                node = node->children[ch];\n                totalScore += node->prefixCount;\n            }\n            scores.push_back(totalScore);\n        }\n        return scores;\n    }\n};\n```\n``` java []\nimport java.util.HashMap;\nimport java.util.List;\nimport java.util.ArrayList;\n\nclass Solution {\n    public List<Integer> sumPrefixScores(List<String> words) {\n        // Build the trie structure from the list of words\n        TrieNode trie = buildTrie(words);\n        // Calculate and return the prefix scores for each word\n        return calculatePrefixScores(trie, words);\n    }\n\n    // Trie node structure\n    private static class TrieNode {\n        HashMap<Character, TrieNode> children = new HashMap<>();\n        int prefixCount = 0;\n    }\n\n    // Build the trie from the words\n    private TrieNode buildTrie(List<String> words) {\n        TrieNode root = new TrieNode();\n        for (String word : words) {\n            TrieNode node = root;\n            for (char ch : word.toCharArray()) {\n                // Navigate through or create nodes in the trie\n                node = node.children.computeIfAbsent(ch, c -> new TrieNode());\n                // Count occurrences of the prefix\n                node.prefixCount++;\n            }\n        }\n        return root;\n    }\n\n    // Calculate prefix scores based on the trie\n    private List<Integer> calculatePrefixScores(TrieNode trie, List<String> words) {\n        List<Integer> scores = new ArrayList<>();\n        for (String word : words) {\n            TrieNode node = trie;\n            int totalScore = 0;\n            for (char ch : word.toCharArray()) {\n                // Move to the next node and accumulate the score\n                node = node.children.get(ch);\n                totalScore += node.prefixCount;\n            }\n            scores.add(totalScore);\n        }\n        return scores;\n    }\n}\n```
['Array', 'String', 'Trie', 'Counting', 'Python', 'C++', 'Java', 'Python3']