Auto-complete feature using Trie

We have a Trie, and when a user enters a character, we have to show the matching string the Trie. This feature we call it as auto-completion. For example, if a Trie contains "xyzzzz,""xyz," "xxxyyxzzz" and when the user enter xy, then we have to show them xyzzzz, xyz, etc..,

Steps to achieve the result.

• Search for the string using the standard Trie algorithm.

• If the string is not present, then return -1.

• If the string is present and is the end of a word in Trie, then print the string.

• If the matching string doesn't have any node, then return.

• Else print all the nodes.

Let's start coding.

# class for Trie Node    class TrieNode():    def __init__(self): # initialising trie node    self.trie_node = {}    self.last_node = False    class Trie():    def __init__(self): # initialising the trie    self.root = TrieNode() # list to store the words    self.words = []    def create_trie(self, keys): # creating the Trie using data    for key in keys: # inserting one key to the trie    self.insert_node(key)    def insert_node(self, key):    node = self.root for obj in list(key):    if not node.trie_node.get(obj):    # creating a TrieNode       node.trie_node[obj] = TrieNode()       node = node.trie_node[obj]    # making leaf node    node.last_node = True    def search(self, key): # searching for the key    node = self.root    is_found = True for obj in list(key):    if not node.trie_node.get(obj):       is_found = False    break       node = node.trie_node[obj] return node and node.last_node and is_found    def matches(self, node, word): if node.last_node:    self.words.append(word) for obj, n in node.trie_node.items():    self.matches(n, word + obj)    def show_auto_completion(self, key):    node = self.root    is_found = False    temp = '' for obj in list(key):    # checking the word if not node.trie_node.get(obj):    is_found = True break    temp += obj    node = node.trie_node[obj] if is_found:    return 0 elif node.last_node and not node.trie_node:    return -1    self.matches(node, temp) for string in self.words:    print(string) return 1    # data for the Trie strings = ["xyz", "xyzzzz", "xyabad", "xyyy", "abc", "abbccc", "xyx", "xyxer", a"]    # word for auto completion    string = "xy"    status = ["Not found", "Found"] # instantiating Trie class    trie = Trie() # creating Trie using the strings    trie.create_trie(strings) # getting the auto completion words for the string from strings    result = trie.show_auto_completion(string) if result == -1 or result == 0:    print("No matches")

If you run the above code, you will get the following result.

xyz xyzzzz xyabad xyyy xyx xyxer