[Python3] Trie - Simple Solution + Detailed Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n- Check for Common Prefix for string -> Trie\n\n# Approach\n Describe your approach to 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Check for Common Prefix for string -> Trie\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n**1. Node Class:**\n\n- Represents a node in the Trie data structure.\n- `cnt_prf` stores the count of prefixes that end at this node.\n- `children` is a dictionary to store child nodes for each character.\n\n**2. Trie Class:**\n\n- Represents the Trie data structure.\n- `root` is the root node of the Trie.\n- `insert(word)` function:\n    - Inserts the given word into the Trie.\n    - Starts from the root node.\n    - Iterates over each character in the word.\n    - Creates a child node if it doesn\'t exist and moves to the child node.\n    - Increments the `cnt_prf` of the current node to indicate that a new prefix ends at this node.\n- `get_sum_prf(word)` function:\n    - Calculates the sum of prefix scores for the given word.\n    - Starts from the root node.\n    - Initializes a counter `cnt` to 0.\n    - Iterates over each character in the word.\n        - If the current character is not found as a child of the current node, breaks the loop (no further prefix exists).\n        - Moves to the child node and adds the `cnt_prf` of the child node to `cnt`.\n    - Returns the final `cnt`, which represents the sum of prefix scores for the word.\n\n**3. Solution Class:**\n\n- `sumPrefixScores(words)` function:\n        - Creates a `Trie` object.\n        - Inserts each word in the given list into the Trie.\n        - Creates a list to store the sum of prefix scores for each word.\n        - Iterates over each word in the list.\n        - Calls `trie.get_sum_prf(word)` to calculate the sum of prefix scores for the current word.\n        - Appends the calculated sum to the result list.\n        - Returns the final list containing the sum of prefix scores for each word.\n\n**Overall Functionality:**\n\nThe Trie is used to efficiently store and retrieve prefixes of the words. By inserting each word into the Trie, the `cnt_prf` values at each node represent the number of words that have the corresponding prefix. The `get_sum_prf` function traverses the Trie for a given word, accumulating the `cnt_prf` values along the path to calculate the total number of prefixes.\n\n# Complexity\n- Time complexity: $$O(N * S)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(26^S)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\nWith `N` is length of `words` and `S` is length of a `word` in `words`\n\n# Code\n```\nclass Node:\n\n    def __init__(self):\n        self.cnt_prf = 0\n        self.children = collections.defaultdict(Node)\n\n\nclass Trie:\n\n    def __init__(self):\n        self.root = Node()\n\n    def insert(self, word: str) -> None:\n        node = self.root\n        for c in word:\n            node = node.children[c]\n            node.cnt_prf += 1\n\n    def get_sum_prf(self, word: str) -> int:\n        node = self.root\n        cnt = 0\n        for c in word:\n            if c not in node.children:break\n            node = node.children[c]\n            cnt += node.cnt_prf\n\n        return cnt\n\n\nclass Solution:\n    def sumPrefixScores(self, words: List[str]) -> List[int]:\n        trie = Trie()\n        for word in words: trie.insert(word)\n        return [trie.get_sum_prf(word) for word in words]\n```
['String', 'Trie', 'Counting', 'Python3']