Python Trie: How To Traverse It To Build List Of All Words?
I have created a trie tree as im learning python, here is the trie output {'a': {'b': {'c': {'_': '_'}}}, 'b': {'a': {'x': {'_': '_'}, 'r': {'_': '_', 'z': {'_': '_'}}, 'z': {'_':
Solution 1:
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']
Solution 2:
In case this is useful to someone, here's a python implementation for generating all strings in a trie if you have a class-based trie.
defbuild_all(root):
l = []
if root:
if root.children:
for node in root.children:
for s in build_all(node):
l.append(str(node.val) + s)
else:
l.append('')
return l
classnode:
def__init__(self, val):
self.val = val
self.children = []
Post a Comment for "Python Trie: How To Traverse It To Build List Of All Words?"