আমাদের কাছে একটি ট্রাই (Trie) আছে, এবং যখন ব্যবহারকারী একটি ক্যারেক্টার ইনপুট দেয়, তবে আমাদের ট্রাই থেকে মিল খুঁজে বের করে দেখাতে হয়। এই ফিচারকে অটো-কমপ্লিশন বলা হয়। উদাহরণস্বরূপ, যদি ট্রাই-তে "xyzzzz", "xyz", "xxxyyxzzz" থাকে এবং ব্যবহারকারী "xy" টাইপ করে, তবে আমাদের "xyzzzz", "xyz" ইত্যাদি দেখাতে হবে।
ফলাফল পাওয়ার ধাপসমূহ:
- স্ট্যান্ডার্ড ট্রাই অ্যালগরিদম ব্যবহার করে স্ট্রিং সার্চ করুন।
- স্ট্রিং না থাকলে -1 রিটার্ন করুন।
- স্ট্রিং থাকলে এবং ট্রাই-এ ওয়ার্ডের শেষে হলে, স্ট্রিংটি প্রিন্ট করুন।
- ম্যাচিং স্ট্রিং-এর কোনো নোড না থাকলে রিটার্ন করুন।
- অন্যথায় সব নোড প্রিন্ট করুন।
কোডিং শুরু করা যাক (পাইথনে):
# 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
# ট্রাই-র ডেটা
strings = ["xyz", "xyzzzz", "xyabad", "xyyy", "abc", "abbccc", "xyx", "xyxer", "a"]
# অটো-কমপ্লিশনের জন্য শব্দ
string = "xy"
status = ["Not found", "Found"]
# Trie ক্লাস ইনস্ট্যানসিয়েট
trie = Trie()
# স্ট্রিংস দিয়ে ট্রাই তৈরি
trie.create_trie(strings)
# অটো-কমপ্লিশন ওয়ার্ড পাওয়া
result = trie.show_auto_completion(string)
if result == -1 or result == 0:
print("No matches")
উপরের কোড রান করলে নিচের ফলাফল আসবে:
xyz xyzzzz xyabad xyyy xyx xyxer
