I created a Trie and when I enter the prefix my autocomplete function can find how many times the prefix included words entered to my tuple and what the word is. But I have a problem with every time when I enter a new prefix, the newly created list appended to my previous lists. For example, this is what I want:

autoComplete('pi) = [ ('pin,1), ('pink,1), ('pine,1),('pinetree,1),('pint,1), ('ping,1) ]

autoComplete('testi) = [ ('testing,2) ]

But my program returns

Completions for "pi" are : [('pin', 1), ('ping', 1), ('pink', 1), ('pine', 1), ('pinetree', 1), ('pint', 1)] Completions for "tes" are : [('pin', 1), ('ping', 1), ('pink', 1), ('pine', 1), ('pinetree', 1), ('pint', 1), ('test', 0), ('testament', 1), ('testing', 2)]

You can find my program below, can you please help me to fix this problem? TY

import sys

# We will use a class called my trie node class TrieRoot: # Initialize some fields def __init__(self,isRootNode): #The initialization below is just a suggestion. #Change it as you will. # But do not change the signature of the constructor. self.isRoot = isRootNode self.isWordEnd = False # is this node a word ending node self.isRoot = False # is this a root node self.children = {} # Dictionary mapping each character from a-z to # the child node if any corresponding to that character. self.count = 0 class MyTrieNode: def __init__(self,isRootNode): self.isRoot= TrieRoot(isRootNode) self.word_list = []

def addWord(self,w): assert(len(w) > 0)

# YOUR CODE HERE # If you want to create helper/auxiliary functions, please do so. current = self.isRoot for i in w: ch = i node = current.children.get(ch) if node == None: node = TrieRoot(True) current.children.update({ch:node}) current = node current.isWordEnd= True current.count +=1 def lookupWord(self,w): # Return frequency of occurrence of the word w in the trie # returns a number for the frequency and 0 if the word w does not occur.

# YOUR CODE HERE currentNode = self.isRoot for i in w: node = currentNode.children.get(i) if node == None: currentNode.count = 0 return currentNode.count currentNode= node if currentNode.isWordEnd == True: return currentNode.count else: return currentNode.count def dfs(self, node, prefix): """Depth-first traversal of the trie Args: - node: the node to start with - prefix: the current prefix, for tracing a word while traversing the trie """ if node.isWordEnd: self.output.append((prefix + node.isRoot, node.count)) for child in node.children.values(): self.dfs(child, prefix + node.isRoot)

def suggestionsRec(self, node, w): if node.isWordEnd: self.word_list.append(w) for a,n in node.children.items(): self.suggestionsRec(n, w + a) def autoComplete(self, w): """Given an input (a prefix), retrieve all words stored in the trie with that prefix, sort the words by the number of times they have been inserted """ node = self.isRoot not_found = False temp_word = '' final = [] for a in list(w): if not node.children.get(a): not_found = True break temp_word += a node = node.children[a] if not_found: return 0 elif node.isWordEnd and not node.children: return -1 self.suggestionsRec(node, temp_word) for s in self.word_list: print(s) final.append((s,self.lookupWord(s))) return final

t= MyTrieNode(True) # Create a root Trie node lst1=['test','testament','testing','ping','pint','pin','pink','pine','pint','testing','pinetree'] # Insert the words in lst1 for w in lst1: t.addWord(w)

lst3 = t.autoComplete('pi') print('Completions for \"pi\" are : ') print(lst3)

lst4 = t.autoComplete('tes') print('Completions for \"tes\" are : ') print(lst4)