I have created a trie tree as im learning python, here is the trie output
{'a': {'b': {'c': {'_': '_'}}}, 'b': {'a': {'x': {'_': '_'}, 'r': {'_': '_', 'z': {'_': '_'}}, 'z': {'_': '_'}}}, 'h': {'e': {'l': {'l': {'o': {'_': '_'}}}}}}
I am unable to list all the words back out of the trie, I'm obviously not understanding something simple, below is my code to create the trie and add to the trie as well as check if words are present in the trie. The method list is my poor attempt to list words, Its only getting the first letter of each word at the moment. Any advice would be super.
# Make My trie
def make_trie(*args):
"""
Make a trie by given words.
"""
trie = {}
for word in args:
if type(word) != str:
raise TypeError("Trie only works on str!")
temp_trie = trie
for letter in word:
temp_trie = temp_trie.setdefault(letter, {})
temp_trie = temp_trie.setdefault('_', '_')
return trie
# Is a word in the trie
def in_trie(trie, word):
"""
Detect if word in trie.
:param word:
:param trie:
"""
if type(word) != str:
raise TypeError("Trie only works on str!")
temp_trie = trie
for letter in word:
if letter not in temp_trie:
return False
temp_trie = temp_trie[letter]
return True
# add to the trie
def add(trie, *args):
for word in args:
if type(word) != str:
raise TypeError("Trie only works on str!")
temp_trie = trie
for letter in word:
temp_trie = temp_trie.setdefault(letter, {})
temp_trie = temp_trie.setdefault('_', '_')
return trie
# My Attempt to list out words
def list(obj, text, words):
str = ""
temp_trie = obj
for index, word in enumerate(temp_trie):
print(temp_trie[word])
if __name__ == '__main__':
trie = make_trie('hello', 'abc', 'baz', 'bar', 'barz')
# print(trie)
# get_file()
words = []
# list(trie, "", words)
print(in_trie(trie, 'bar'))
print(in_trie(trie, 'bab'))
print(in_trie(trie, 'zzz'))
add(trie, "bax")
print(in_trie(trie, 'bax'))
print(in_trie(trie, 'baz'))
print(trie)
list(trie, "", 'hello')
The expected output i would like is a list of words present in the trie
like so
content = ['hello', 'abc', 'baz', 'bar', 'barz']
解決方案
You should write a recursive function that searches the tree
def list_words(trie):
my_list = []
for k,v in trie.items():
if k != '_':
for el in list_words(v):
my_list.append(k+el)
else:
my_list.append('')
return my_list
example output
>>> trie = {'a': {'b': {'c': {'_': '_'}}}, 'b': {'a': {'x': {'_': '_'}, 'r': {'_': '_', 'z': {'_': '_'}}, 'z': {'_': '_'}}}, 'h': {'e': {'l': {'l': {'o': {'_': '_'}}}}}}
>>> print(list_words(trie))
['abc', 'hello', 'bax', 'barz', 'bar', 'baz']