数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚学习
法律学习使用 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 次浏览
广告