implement_trie_prefix_tree
1from collections import defaultdict 2 3 4# @leet start 5class Node: 6 def __init__(self): 7 self.is_word = False 8 self.children = defaultdict(Node) 9 10 11class Trie: 12 """ 13 This question asks us to implement a trie, a data structure for fast 14 prefix searching. 15 16 To do this, we first create a Node class, which has only two members, its 17 children and whether or not it is the end of a word. 18 19 The node's children will be a defaultdict of Node, so it will be char -> Node. 20 21 When inserting a new word, we take the Trie's root (a dummy node), and then 22 for every character, we set its child to a new node if we haven't seen that character before, 23 otherwise, we simply move onto the next child node. 24 25 If we search for a word, for every character in the word, we check if it exists 26 in each node, and then check if our final pointer indicates it is a word. 27 28 StartsWith is the same, we just dont have to check if the curr pointer is a word. 29 """ 30 31 def __init__(self): 32 self.root = Node() 33 34 def insert(self, word: str) -> None: 35 curr = self.root 36 for c in word: 37 if c not in curr.children: 38 curr.children[c] = Node() 39 curr = curr.children[c] 40 curr.is_word = True 41 42 def search(self, word: str) -> bool: 43 curr = self.root 44 for c in word: 45 if c not in curr.children: 46 return False 47 curr = curr.children[c] 48 return curr.is_word 49 50 def startsWith(self, prefix: str) -> bool: 51 curr = self.root 52 for c in prefix: 53 if c not in curr.children: 54 return False 55 curr = curr.children[c] 56 return True 57 58 59# Your Trie object will be instantiated and called as such: 60# obj = Trie() 61# obj.insert(word) 62# param_2 = obj.search(word) 63# param_3 = obj.startsWith(prefix) 64# @leet end 65 66 67def test(): 68 assert 2 + 2 == 4
class
Node:
class
Trie:
12class Trie: 13 """ 14 This question asks us to implement a trie, a data structure for fast 15 prefix searching. 16 17 To do this, we first create a Node class, which has only two members, its 18 children and whether or not it is the end of a word. 19 20 The node's children will be a defaultdict of Node, so it will be char -> Node. 21 22 When inserting a new word, we take the Trie's root (a dummy node), and then 23 for every character, we set its child to a new node if we haven't seen that character before, 24 otherwise, we simply move onto the next child node. 25 26 If we search for a word, for every character in the word, we check if it exists 27 in each node, and then check if our final pointer indicates it is a word. 28 29 StartsWith is the same, we just dont have to check if the curr pointer is a word. 30 """ 31 32 def __init__(self): 33 self.root = Node() 34 35 def insert(self, word: str) -> None: 36 curr = self.root 37 for c in word: 38 if c not in curr.children: 39 curr.children[c] = Node() 40 curr = curr.children[c] 41 curr.is_word = True 42 43 def search(self, word: str) -> bool: 44 curr = self.root 45 for c in word: 46 if c not in curr.children: 47 return False 48 curr = curr.children[c] 49 return curr.is_word 50 51 def startsWith(self, prefix: str) -> bool: 52 curr = self.root 53 for c in prefix: 54 if c not in curr.children: 55 return False 56 curr = curr.children[c] 57 return True
This question asks us to implement a trie, a data structure for fast prefix searching.
To do this, we first create a Node class, which has only two members, its children and whether or not it is the end of a word.
The node's children will be a defaultdict of Node, so it will be char -> Node.
When inserting a new word, we take the Trie's root (a dummy node), and then for every character, we set its child to a new node if we haven't seen that character before, otherwise, we simply move onto the next child node.
If we search for a word, for every character in the word, we check if it exists in each node, and then check if our final pointer indicates it is a word.
StartsWith is the same, we just dont have to check if the curr pointer is a word.
def
test():