Created
January 5, 2017 03:16
-
-
Save MathisHammel/5300cc4404870eb4f01702ebd818463e to your computer and use it in GitHub Desktop.
Simple implementation of a trie to show phone number autocompletion
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 Trie: | |
def __init__(self): | |
self.children={} | |
self.label=None | |
def findall(self): | |
matches=set() | |
if self.label!=None: | |
matches.add(self.label) | |
for child in self.children: | |
matches |= self.children[child].findall() | |
return matches | |
def find(self,digits): | |
if len(digits)==0: | |
return self.findall() #Return all labels in the current subtree | |
if digits[0] not in self.children: | |
return set() | |
else: | |
return self.children[digits[0]].find(digits[1:]) | |
def insert(self,digits,name): | |
if len(digits)>0: | |
if digits[0] not in self.children: | |
self.children[digits[0]]=Trie() | |
self.children[digits[0]].insert(digits[1:],name) | |
else: | |
self.label=name | |
if __name__=='__main__': | |
directoryDict={'5550123':'Paul', | |
'5584586':'Ryan', | |
'911':'Police', | |
'5550456':'Liam', | |
'9110221':'Henry'} | |
directoryTrie=Trie() | |
for number,name in directoryDict.iteritems(): | |
directoryTrie.insert(number,name) | |
print directoryTrie.find('555') | |
print directoryTrie.find('9110') | |
print directoryTrie.find('131') |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment