Created
May 2, 2017 19:21
-
-
Save seporaitis/b604893f4759e626ce2e74b303d3300a to your computer and use it in GitHub Desktop.
Simple tries implementation in python
This file contains hidden or 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
#!/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