Cho một Trie, khi người dùng nhập ký tự, hiển thị chuỗi khớp trong Trie. Tính năng này gọi là auto-completion. Ví dụ: Trie chứa "xyzzzz", "xyz", "xxxyyxzzz", người dùng nhập "xy" → hiển thị "xyzzzz", "xyz", v.v.
Các bước thực hiện:
- Tìm chuỗi bằng thuật toán Trie chuẩn.
- Nếu không có → trả về -1.
- Nếu có và là cuối từ trong Trie → in chuỗi.
- Nếu node khớp không có node con → trả về.
- Ngược lại in tất cả node con.
Bắt đầu code (Python):
# class for Trie Node
class TrieNode():
def __init__(self):
self.trie_node = {}
self.last_node = False
class Trie():
def __init__(self):
self.root = TrieNode()
self.words = []
def create_trie(self, keys):
for key in keys:
self.insert_node(key)
def insert_node(self, key):
node = self.root
for obj in list(key):
if not node.trie_node.get(obj):
node.trie_node[obj] = TrieNode()
node = node.trie_node[obj]
node.last_node = True
def search(self, 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):
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 Trie
strings = ["xyz", "xyzzzz", "xyabad", "xyyy", "abc", "abbccc", "xyx", "xyxer", "a"]
string = "xy"
status = ["Not found", "Found"]
trie = Trie()
trie.create_trie(strings)
result = trie.show_auto_completion(string)
if result == -1 or result == 0:
print("No matches")
Chạy code cho kết quả:
xyz xyzzzz xyabad xyyy xyx xyxer