Skip to content

Instantly share code, notes, and snippets.

@anish000kumar
Last active July 19, 2020 04:23
Show Gist options
  • Save anish000kumar/a336c360c50144eab63954d97bd7f8e6 to your computer and use it in GitHub Desktop.
Save anish000kumar/a336c360c50144eab63954d97bd7f8e6 to your computer and use it in GitHub Desktop.
Trie implementation in python
class Node:
def __init__(self, val=None):
self.val = val
self.children = {}
self.count = 0. # number of times words with this prefix
self.end = 0 # number of times this word has been inserted
class Trie:
def __init__(self):
self.root = Node()
def insert(self, word: str) -> None:
for ch in word:
if ch not in curr.children:
curr.children[ch] = Node(ch)
curr.children[ch] += 1
curr = curr.children[ch]
curr.end += 1
def search(self, word: str) -> bool:
curr = self.root
for ch in word:
if ch not in curr.children:
return False
curr = curr.children[ch]
if curr.end == True: return True
def startsWith(self, prefix: str) -> bool:
curr = self.root
for ch in prefix:
if ch not in curr.children:
return False
curr = curr.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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment