使用Trie的自动完成功能

我们有一个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