Last active
October 11, 2020 23:02
-
-
Save akshaynagpal/1905768c6571f01c16bb4bc57eb8e48d to your computer and use it in GitHub Desktop.
Trie implementation in Python 3 from scratch
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class TrieNode: | |
def __init__(self): | |
self.children = {} | |
self.isEndOfWord = False | |
class Trie: | |
def __init__(self): | |
self.root = TrieNode() | |
def insertWord(self, word): | |
currNode = self.root | |
while word: | |
if word[0] not in currNode.children: | |
currNode.children[word[0]] = TrieNode() | |
currNode = currNode.children[word[0]] | |
word = word[1:] | |
currNode.isEndOfWord = True | |
def search(self, word): | |
currNode = self.root | |
while word: | |
if word[0] not in currNode.children: | |
return False | |
else: | |
currNode = currNode.children[word[0]] | |
word = word[1:] | |
return currNode.isEndOfWord | |
trie = Trie() | |
trie.insertWord("hell") | |
trie.insertWord("hello") | |
trie.insertWord("bye") | |
trie.insertWord("") | |
assert(trie.search("") == True) # should return True | |
assert(trie.search("bye") == True) # should return True | |
assert(trie.search("hell") == True) # should return True | |
assert(trie.search("hello") == True) # should return True | |
assert(trie.search("by") == False) # should return False |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
It was fun trying to implement a simple trie class in python. Star it if it was useful for you, feels nice getting a star from an internet stranger :)