Skip to content

Instantly share code, notes, and snippets.

@MathisHammel
Created January 5, 2017 03:16
Show Gist options
  • Save MathisHammel/5300cc4404870eb4f01702ebd818463e to your computer and use it in GitHub Desktop.
Save MathisHammel/5300cc4404870eb4f01702ebd818463e to your computer and use it in GitHub Desktop.
Simple implementation of a trie to show phone number autocompletion
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