0208-implement-trie-prefix-tree.py

classTrieNode:
def__init__(self):
self.children= [None] *26
self.end=False


classTrie:
def__init__(self):
"""
 Initialize your data structure here.
 """
self.root=TrieNode()

definsert(self, word: str) ->None:
"""
 Inserts a word into the trie.
 """
curr=self.root
forcinword:
i=ord(c) -ord("a")
ifcurr.children[i] ==None:
curr.children[i] =TrieNode()
curr=curr.children[i]
curr.end=True

defsearch(self, word: str) ->bool:
"""
 Returns if the word is in the trie.
 """
curr=self.root
forcinword:
i=ord(c) -ord("a")
ifcurr.children[i] ==None:
returnFalse
curr=curr.children[i]
returncurr.end

defstartsWith(self, prefix: str) ->bool:
"""
 Returns if there is any word in the trie that starts with the given prefix.
 """
curr=self.root
forcinprefix:
i=ord(c) -ord("a")
ifcurr.children[i] ==None:
returnFalse
curr=curr.children[i]
returnTrue