LeetCode: Implement Trie (Prefix Tree) Posted on January 19, 2018July 26, 2020 by braindenny Implement Trie (Prefix Tree) Similar Problems: CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #oodesign, #trie Implement a trie with insert, search, and startsWith methods. Note: You may assume that all inputs are consist of lowercase letters a-z. Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. ## https://code.dennyzhang.com/implement-trie-prefix-tree ## Basic Ideas: TrieNode: is_word(bool), children(dict) ## For the root node, we don't store any characters. Only in children ## Here we use defaultdict, thus we can avoid has_key check ## Assumption: If one word in the Trie tree, we also treat it starts with the word. ## Complexity: class TrieNode(object): def __init__(self): self.children = collections.defaultdict(TrieNode) self.is_word = False class Trie(object): def __init__(self): """ Initialize your data structure here. """ self.root = TrieNode() def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ node = self.root # check character by character for ch in word: node = node.children[ch] node.is_word = True def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ node = self.root for ch in word: if ch not in node.children: return False node = node.children[ch] return node.is_word def startsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ node = self.root for ch in prefix: if ch not in node.children: return False node = node.children[ch] return True # Your Trie object will be instantiated and called as such: # obj = Trie() # obj.insert(word) # param_2 = obj.search(word) # param_3 = obj.startsWith(prefix) Post Views: 4