String hashing | No trie needed | Python3
Intuition\nWe can use a rolling hash to cumulatively calculate the hash of all the prefixes in O(len(word)).\nThus, we can store the occurences of this hash in 
# Intuition\nWe can use a rolling hash to cumulatively calculate the hash of all the prefixes in O(len(word)).\nThus, we can store the occurences of this hash in various strings and lookup the counts in a second loop to calculate the score.\n\n# Complexity\n- Time complexity:\nO(len(words) * len(word))\n\n- Space complexity:\nO(len(words) * len(word))\n\n# Code\n```python3 []\nclass Solution:\n    def sumPrefixScores(self, words: List[str]) -> List[int]:\n        M, P = 10**15 + 7, 31\n        prefix_hash_dict = defaultdict(int)\n\n        def idx(char):\n            return ord(char) - ord(\'a\') + 1\n\n        def encode_prefixes(s):\n            prefix_hash = 0\n            p = 1\n            for char in s:\n                prefix_hash = (prefix_hash + idx(char) * p) % M\n                prefix_hash_dict[prefix_hash] += 1\n                p = (p * P) % M\n\n        def score(s):\n            prefix_hash = res = 0\n            p = 1\n            for char in s:\n                prefix_hash = (prefix_hash + idx(char) * p) % M\n                res += prefix_hash_dict[prefix_hash]\n                p = (p * P) % M\n            return res\n\n        for word in words:\n            encode_prefixes(word)\n\n        return [score(word) for word in words]\n\n```
['Hash Table', 'Trie', 'Rolling Hash', 'Python3']