คุณสมบัติเติมข้อความอัตโนมัติโดยใช้ 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