使用 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

更新日期：2020 年 9 月 21 日

468 次浏览

开启 职业生涯

完成课程获得认证

开始
广告