Python | Trie | Modular clean code
Standard Trie implmentation, which I follow to solve all the Trie problems with just slight variation in search and insert method as per problem statement. Maki
Standard Trie implmentation, which I follow to solve all the Trie problems with just slight variation in search and insert method as per problem statement. Making a habit to follow a template makes you fast and well organized and it leaves the best impression on interviewer.\n\nSolution inspired from: https://leetcode.com/problems/sum-of-prefix-scores-of-strings/discuss/2590701/Concise-Python-Tire-Implementation\n\nIntuition: While inserting words in Trie, maintain a count of all the prefixes and just sum them up while performing search for each word and each prefix. We can also add a memo dict to keep count of already explored prefixes that will help reduce time complexity but will increase space complexity. A trade-off to choose from but a must to mention during interviews.\n\nn = len(words)\nm = len(max(words))\n\nTime Complexity:\nInsert: O(mn) \nSearch: O(mn), traversing all the nodes of tree\n\nSC: O(mn), from storing it in trie\n\n```\nclass Node:\n    def __init__(self):\n        self.children = {}\n        self.isWord = False\n        self.count = 0\n\nclass Trie:\n    def __init__(self):\n        self.root = Node()\n    \n    def insert(self, word):\n        node = self.root\n        \n        for ch in word:\n            if ch not in node.children:\n                node.children[ch] = Node()\n\t\t\t# Increment occurrence of the current prefix in Trie\n            node.children[ch].count += 1\n            node = node.children[ch]\n        \n        node.isWord = True\n    \n    def search(self, word) -> int :\n        score = 0\n        node = self.root\n        \n        for ch in word:\n\t\t\t# Add count for current prefix \n            score += node.count\n            node = node.children[ch]\n\t\t\t\n        # Add count for current word          \n        score += node.count\n            \n        return score\n\nclass Solution:\n    def sumPrefixScores(self, words: List[str]) -> List[int]:\n        \n        trie = Trie()\n        \n        # Insert word in to trie\n        for word in words:\n            trie.insert(word)\n        \n        scores =[]\n        # Search words for all prefixes of current word\n        for word in words:\n            scores.append(trie.search(word))\n        \n        return scores\n        \n```
['String', 'Trie', 'Python', 'Python3']