Python | Trie-based Pattern
see the Successfully Accepted Submission\n\n# Code\npython3 []\nclass TrieNode:\n    def __init__(self):\n        self.children = {}\n        self.prefix_count 
[see the Successfully Accepted Submission](https://leetcode.com/problems/sum-of-prefix-scores-of-strings/submissions/1401354774/?envType=daily-question&envId=2024-09-25)\n\n# Code\n```python3 []\nclass TrieNode:\n    def __init__(self):\n        self.children = {}\n        self.prefix_count = 0\n\nclass Solution:\n    def sumPrefixScores(self, words: List[str]) -> List[int]:\n        # Step 1: Build the Trie\n        root = TrieNode()\n        \n        # Insert each word into the trie and track the prefix counts\n        for word in words:\n            current = root\n            for char in word:\n                if char not in current.children:\n                    current.children[char] = TrieNode()\n                current = current.children[char]\n                current.prefix_count += 1  # Increment the prefix count at each node\n        \n        # Step 2: For each word, calculate the total prefix score\n        result = []\n        for word in words:\n            current = root\n            score = 0\n            for char in word:\n                current = current.children[char]\n                score += current.prefix_count  # Sum the prefix counts for each character in the word\n            result.append(score)\n        \n        return result\n\n```\n\n# Solution Approach:\n\n### Trie Data Structure:\nWe will insert each word into a trie, and at each node, we\'ll keep track of how many words pass through that node (i.e., how many words have that prefix).\n\n### Prefix Count:\nWhile inserting a word into the trie, for each prefix of that word (as we traverse the characters), we increment a counter at that node.\n\n### Querying the Trie:\nAfter building the trie, for each word, we can sum up the prefix counts by traversing the trie again from the root to the end of the word.\n\nThis will allow us to compute the scores for all the words in a time-efficient manner.\n\n## Steps:\n\n1. **Step 1**: Build a trie from the list of words where each node keeps track of how many words have a common prefix up to that point.\n2. **Step 2**: For each word, traverse the trie to compute the sum of scores for all its prefixes.\n\n---\n\n## Explanation of the Code:\n\n### TrieNode Class:\nEach node in the trie contains:\n- **children**: A dictionary to store the child nodes for each character.\n- **prefix_count**: An integer that tracks how many words have this prefix.\n\n### Building the Trie:\n- We iterate through each word, and for each character in the word, we insert it into the trie.\n- While inserting, we increment the `prefix_count` for each node (character) we visit.\n\n### Querying the Trie:\n- For each word, we traverse the trie from the root to the last character of the word, summing the `prefix_count` for each node along the way.\n- This gives us the total score for that word.\n\n---\n\n## Time Complexity:\n\n- **Trie Insertion**: Inserting each word into the trie takes `O(m)` time, where `m` is the length of the word. Since we have `n` words, and the maximum word length is `L`, the total time for building the trie is `O(n * L)`.\n\n- **Prefix Score Calculation**: For each word, we again traverse its length, which takes `O(L)` time. Hence, for all words, this is `O(n * L)`.\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']