Skip to content

Instantly share code, notes, and snippets.

@seporaitis
Created May 2, 2017 19:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save seporaitis/b604893f4759e626ce2e74b303d3300a to your computer and use it in GitHub Desktop.
Save seporaitis/b604893f4759e626ce2e74b303d3300a to your computer and use it in GitHub Desktop.
Simple tries implementation in python
#!/usr/bin/env python3
class Node(dict):
def __init__(self, *args, **kwargs):
super(*args, **kwargs)
self.end = kwargs.get('end', False)
def add_word(self, word):
if not word:
self.end = True
return
if word[0] not in self:
self[word[0]] = Node()
self[word[0]].add_word(word[1:])
def find_word(self, word):
if not word:
return self.end
if word[0] in self:
return self[word[0]].find_word(word[1:])
return False
def get_all_words(self):
if self.end:
return [""]
result = []
for char, node in self.items():
result.extend([char + x for x in node.get_all_words()])
return result
def __str__(self):
result = ""
alphabetical = [char for char in self]
alphabetical.sort()
for char in alphabetical:
result += "['{}': {}{}]".format(char, str(self[char]), "." if self[char].end else "")
return result
if __name__ == '__main__':
t = Node()
t.add_word('ace')
t.add_word('actor')
t.add_word('brie')
assert str(t) == "['a': ['c': ['e': .]['t': ['o': ['r': .]]]]]['b': ['r': ['i': ['e': .]]]]"
assert t.find_word('') == False
assert t.find_word('ac') == False
assert t.find_word('ace') == True
assert t.find_word('actor') == True
assert t.find_word('acclaim') == False
assert t.find_word('brieyonce') == False
assert t.find_word('brie') == True
assert len(t) == 2
assert len(t['a']) == 1
assert len(t['a']['c']) == 2
assert set(t.get_all_words()) == set(['actor', 'ace', 'brie'])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment