Concise and beautiful Trie | Cracking Hard into Easy
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \nJust use a custom Trie,
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nJust use a custom Trie, with infomation of `count` as the number of words in `words` which also has this character\n\n# Complexity\n- Time complexity: O(n * k)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n * k)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Node:\n    def __init__(self):\n        self.children = {}\n        self.count = 0\nclass Trie:\n    def __init__(self):\n        self.root = Node()\n    \n    def add_word(self, word):\n        cur = self.root\n        for c in word:\n            if c not in cur.children:\n                cur.children[c] = Node()\n            cur = cur.children[c]\n            cur.count += 1\n    \n    def get_sum_score(self, word):\n        cur = self.root\n        total = 0\n        for c in word:\n            if c not in cur.children:\n                return total\n            cur = cur.children[c]\n            total += cur.count\n        return total\n        \nclass Solution:\n    def sumPrefixScores(self, words: List[str]) -> List[int]:\n        trie = Trie()\n        for word in words:\n            trie.add_word(word)\n        res = []\n        for word in words:\n            res.append(trie.get_sum_score(word))\n        return res\n```
['String', 'Trie', 'Python3']