I need to add the ability to list suffixes to implement our autocomplete feature. To do that, I implemented a function on the TrieNode object that will return all complete word suffixes that exist below it in the trie. For example, if our Trie contains the words ["fun", "function", "factory"] and we ask for suffixes from the f node, we would expect to receive ["un", "unction", "actory"] back from node.get_suffixes(). Here is how I get started:
class TrieNode:
def __init__(self):
## Initialize this node in the Trie
self.word_end = False
self.children = dict()
def insert(self, char):
## Add a child node in this Trie
if not char in self.children:
self.children[char] = TrieNode()
def get_suffixes(self):
pass
I have tested the get_suffixes function separately and it seemed to work fine.
result = []
def get_suffixes(node, suffix=""):
if not node.children == dict():
for key in node.children:
suffix += key
if node.children[key].word_end:
result.append(suffix)
get_suffixes(node.children[key], suffix)
suffix = suffix[:-1]
return result
How is how I tested the function:
# Create a mock trie for the test
node = TrieNode()
node.insert("A")
node.children["A"].word_end = True
node.children["A"].insert("t")
node.children["A"].children["t"].word_end = True
node.children["A"].insert("b")
node.children["A"].children["b"].insert("a")
node.children["A"].children["b"].children["a"].insert("c")
node.children["A"].children["b"].children["a"].children["c"].insert("a")
node.children["A"].children["b"].children["a"].children["c"].children["a"].word_end = True
node.children["A"].insert("d")
node.children["A"].children["d"].insert("d")
node.children["A"].children["d"].children["d"].word_end = True
node.children["A"].children["d"].insert("m")
node.children["A"].children["d"].children["m"].insert("i")
node.children["A"].children["d"].children["m"].children["i"].insert("n")
node.children["A"].children["d"].children["m"].children["i"].children["n"].word_end = True
result = []
def get_suffixes(node, suffix=""):
if not node.children == dict():
for key in node.children:
suffix += key
if node.children[key].word_end:
result.append(suffix)
get_suffixes(node.children[key], suffix)
suffix = suffix[:-1]
return result
get_suffixes(node.children["A"]) # Returns ['t', 'baca', 'dd', 'dmin'], as expected
The problem occured when I tried moving the get_suffixes function to the TrieNode class. Here I do not know how I should tackle the global variable result. It is not supposed to be a global variable anymore. I have tried two versions:
Version I: make result a class attribute
class TrieNode:
def __init__(self):
## Initialize this node in the Trie
self.word_end = False
self.children = dict()
self.result = []
def insert(self, char):
## Add a child node in this Trie
if not char in self.children:
self.children[char] = TrieNode()
def get_suffixes(self, suffix=""):
if not self.children == dict():
for key in self.children:
suffix += key
if self.children[key].word_end:
self.result.append(suffix)
self.children[key].get_suffixes(suffix)
suffix = suffix[:-1]
return self.result
node.children["A"].get_suffixes() # Returns ['t'], which is wrong
Version II: make result a default function parameter
class TrieNode:
def __init__(self):
## Initialize this node in the Trie
self.word_end = False
self.children = dict()
def insert(self, char):
## Add a child node in this Trie
if not char in self.children:
self.children[char] = TrieNode()
def suffixes(self, suffix="", result=[]):
if not self.children == dict():
for key in self.children:
suffix += key
if self.children[key].word_end:
result.append(suffix)
self.children[key].suffixes(suffix)
suffix = suffix[:-1]
return result
node.children["A"].suffixes() # Returns ['t', 'baca', 'dd', 'dmin']
node.children["A"].suffixes() # Returns ['t', 'baca', 'dd', 'dmin', 't', 'baca', 'dd', 'dmin']
The result of Version II is not surprising because:
def append(number, number_list=[]):
number_list.append(number)
print(number_list)
return number_list
append(5) # expecting: [5], actual: [5]
append(7) # expecting: [7], actual: [5, 7]
append(2) # expecting: [2], actual: [5, 7, 2]
I am learning algorithms and data structure in Python. I was asked to do it using a recursive function. Other approaches such as Implementing a Trie to support autocomplete in Python are not the answers I expect though they themselves might be able to solve the problem. I am extremely curious why self.result is not properly modified in Version I but works properly if it does not reside in a class.
