Trie, just 3 steps
Intuition\n Describe your first thoughts on how to solve this problem. \nTo solve this problem, you need to efficiently calculate the number of times each prefi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo solve this problem, you need to efficiently calculate the number of times each prefix of a given string appears in the list of words. A direct approach could involve checking each prefix of each string against all words, but this would be too slow. Instead, using a Trie (prefix tree) is a more efficient way to keep track of prefix frequencies.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Trie Construction:\n\n* Use a Trie data structure to store all words. In this Trie, each node represents a character in the words, and we will maintain a count of how many times each prefix is encountered.\n2. Inserting Words into Trie:\n\n* For each word, insert it into the Trie. During insertion, for each character in the word, increment the char_count at the corresponding Trie node. This count will help us determine how many words share that prefix.\n3. Calculate Prefix Scores:\n\n* For each word in the list, traverse the Trie to calculate the sum of the scores for all non-empty prefixes of the word. This can be done by accumulating the counts of each prefix as you traverse the Trie.\n\n# Complexity\n- Time complexity: O(nxm)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(m)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass TrieNode:\n    def __init__(self):\n        self.children = {}\n        self.is_end_of_word = False\n        self.char_count = 0\n\nclass Trie:\n    def __init__(self):\n        self.root = TrieNode()\n    \n    def insert(self, word):\n        node = self.root\n        for char in word:\n            if char not in node.children:\n                node.children[char] = TrieNode()\n            node = node.children[char]\n            node.char_count += 1\n        node.is_end_of_word = True\n\n    def search(self, word):\n        node = self.root\n        ans = 0\n        for char in word:\n            node = node.children[char]\n            ans += node.char_count\n        return ans\n\n\nclass Solution:\n    def sumPrefixScores(self, words: List[str]) -> List[int]:\n        trie = Trie()\n        for x in words:\n            trie.insert(x)\n        l = []\n        for x in words:\n            l.append(trie.search(x))\n        return l\n\n```
['Python3']