আমাদের একটি ট্রাই আছে, এবং যখন একজন ব্যবহারকারী একটি অক্ষর প্রবেশ করে, তখন আমাদের ট্রাই-এর সাথে মিলে যাওয়া স্ট্রিংটি দেখাতে হবে। এই বৈশিষ্ট্যটিকে আমরা স্বয়ংক্রিয়-সম্পূর্ণতা বলে থাকি। উদাহরণস্বরূপ, যদি একটি Trie তে "xyzzzz,""xyz," "xxxyyxzzz" থাকে এবং যখন ব্যবহারকারী xy লিখবেন , তারপর আমাদের তাদের xyzzzz, xyz দেখাতে হবে , ইত্যাদি..,
ফলাফল অর্জনের পদক্ষেপ।
-
স্ট্যান্ডার্ড ট্রাই অ্যালগরিদম ব্যবহার করে স্ট্রিং অনুসন্ধান করুন৷
-
যদি স্ট্রিংটি উপস্থিত না থাকে, তাহলে -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
