Chúng tôi có một Trie và khi người dùng nhập một ký tự, chúng tôi phải hiển thị chuỗi phù hợp là Trie. Tính năng này chúng tôi gọi nó là tự động hoàn thành. Ví dụ:nếu một Trie chứa "xyzzzz", "xyz", "xxxyyxzzz" và khi người dùng nhập xy , sau đó chúng tôi phải hiển thị cho họ xyzzzz, xyz , v.v ..,
Các bước để đạt được kết quả.
-
Tìm kiếm chuỗi bằng thuật toán Trie tiêu chuẩn.
-
Nếu chuỗi không có, thì trả về -1.
-
Nếu chuỗi có mặt và là phần cuối của một từ trong Trie, thì hãy in chuỗi.
-
Nếu chuỗi phù hợp không có bất kỳ nút nào, hãy trả về.
-
Nếu không, hãy in tất cả các nút.
Hãy bắt đầu viết mã.
# 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") Nếu bạn chạy đoạn mã trên, bạn sẽ nhận được kết quả sau.
xyz xyzzzz xyabad xyyy xyx xyxer