เรามี Trie และเมื่อผู้ใช้ป้อนตัวอักษร เราต้องแสดงสตริงที่ตรงกันใน Trie ฟีเจอร์นี้เรียกว่า auto-completion ตัวอย่างเช่น หาก Trie มี "xyzzzz," "xyz," "xxxyyxzzz" และผู้ใช้ป้อน xy เราต้องแสดง xyzzzz, xyz ฯลฯ
ขั้นตอนเพื่อให้ได้ผลลัพธ์:
ค้นหาสตริงด้วย standard Trie algorithm
หากสตริงไม่มี ให้คืนค่า -1
หากสตริงมีอยู่และเป็น end of a word ใน Trี ให้พิมพ์สตริงนั้น
หากสตริงที่ตรงกันไม่มี node ให้ return
มิฉะนั้น พิมพ์ทุก node
เริ่มเขียนโค้ด
# 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
