我们有一个Trie,当用户输入一个字符时,我们必须显示匹配的字符串Trie。我们称其为自动完成功能。例如,如果Trie包含“ xyzzzz”,“ xyz”,“ xxxyyxzzz”,并且当用户输入xy时,我们必须向他们显示xyzzzz,xyz等。
实现结果的步骤。
使用标准Trie算法搜索字符串。
如果字符串不存在,则返回-1。
如果该字符串存在并且是Trie中单词的结尾,则打印该字符串。
如果匹配的字符串没有任何节点,则返回。
否则打印所有节点。
让我们开始编码。
# 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")
如果运行上面的代码,您将得到以下结果。
xyz xyzzzz xyabad xyyy xyx xyxer