Sum of Prefix Scores of Strings
\n# Approach\n Describe your approach to solving the problem. \nHashMap and Trie\n\n\n\n# Time complexity:\n Add your time complexity here, e.g. O(n) \n- Hashma
\n# Approach\n<!-- Describe your approach to solving the problem. -->\n**HashMap** and **Trie**\n\n\n\n# Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- **Hashmap**: O(n * k\xB2)\n    \n\n- **Trie**: O(n * k)\n\n\n\n#  Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n- **Hashmap**: O(n * k)\n\n- **Trie**: O(n * k)\n\n\nFor anyone wondering why it\'s O(n * k\xB2) for the hashmap, it\'s because for each of the n words, generating all k prefixes requires slicing the string, which takes O(k) time per slice, leading to O(k\xB2) operations for each word\n\n# Code\n```python3 []\nfrom collections import defaultdict\n\n# TrieNode class that defines the structure of each node in the Trie.\nclass TrieNode:\n    def __init__(self):\n        self.children = {}\n        self.counter = 0\n\nclass Solution:\n    def sumPrefixScores(self, words: List[str]) -> List[int]:\n    # Method 1: Using HashMap \n    # This approach uses a hash map to store the count of each prefix.\n    # It\'s simple but inefficient in terms of memory and time due to repeated prefix calculations.\n    # Time complexity: O(n * k^2)\n    # Space complexity: O(n * k)\n        # h = defaultdict(int)\n        # for word in words:\n        #     for j in range(1, len(word) + 1):\n        #         h[word[:j]] += 1\n        \n    # # Calculate the prefix scores by summing the counts of all prefixes for each word.\n        # res = []\n        # for word in words:\n        #     total = 0\n        #     for j in range(1, len(word) + 1):\n        #         total += h[word[:j]]\n        #     res.append(total)\n        \n        # return res\n\n    # Method 2: Using Trie (optimized approach)\n    # This approach uses a Trie data structure to store prefixes and calculate their frequency efficiently.\n    # Time complexity: O(n * k)\n    # Space complexity: O(n * k)\n        trie = TrieNode()  \n\n    # Step 1: Build the Trie and count how many words pass through each prefix.\n        for word in words:\n            cur = trie  \n            for char in word:\n                if char not in cur.children:\n                    cur.children[char] = TrieNode()  \n                cur = cur.children[char]  \n                cur.counter += 1  \n\n    # Step 2: Calculate the prefix score for each word by summing up the counters of its prefixes.\n        res = []\n        for word in words:\n            cur = trie  \n            total = 0  \n            for char in word:\n                cur = cur.children[char]  \n                total += cur.counter  \n            res.append(total) \n\n        return res\n\n```
['Trie', 'Counting', 'Python3']