資料結構
網路
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 次瀏覽
廣告