ধরুন আমাদের তিনটি মৌলিক অপারেশন যেমন insert(), search(), startsWith() মেথড দিয়ে trie গঠন করতে হবে। আমরা অনুমান করতে পারি যে সমস্ত ইনপুট ছোট হাতের অক্ষরে রয়েছে। উদাহরণস্বরূপ, যদি আমরা ফাংশনগুলিকে নিম্নরূপ কল করি, আমরা আউটপুট দেখতে পাব
- Trie trie =নতুন Trie()
- trie.insert(“apple”)
- trie.search(“apple”) //এটি সত্য হবে
- trie.search("app") //এটি মিথ্যা ফেরত দেবে
- trie.startsWith(“app”) //এটি সত্য হবে
- trie.insert(“app”)
- trie.search("app") //এটি সত্য হবে
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- প্রাথমিকভাবে শিশু নামে একটি অভিধান তৈরি করুন।
- সন্নিবেশ পদ্ধতি হবে − এর মত
- বর্তমান :=শিশু
- প্রতিটি অক্ষরের জন্য l শব্দে −
- যদি l বর্তমানের মধ্যে উপস্থিত না থাকে, তাহলে বর্তমান[l] :=নতুন অভিধান
- কারেন্ট :=বর্তমান[l]
- বর্তমান[#] =1
- অনুসন্ধান পদ্ধতি হবে − এর মত
- বর্তমান :=শিশু
- প্রতিটি অক্ষরের জন্য l শব্দে −
- যদি l কারেন্টে উপস্থিত না থাকে, তাহলে মিথ্যা ফেরত দিন
- কারেন্ট :=বর্তমান[l]
- কারেন্ট [#] =1 হলে সত্য ফেরত দিন, অন্যথায় মিথ্যা
- StartsWith পদ্ধতির মত হবে −
- বর্তমান :=শিশু
- প্রতিটি অক্ষরের জন্য l শব্দে −
- যদি l কারেন্টে উপস্থিত না থাকে, তাহলে মিথ্যা ফেরত দিন
- কারেন্ট :=বর্তমান[l]
- সত্য ফেরান
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class Trie(object):
def __init__(self):
self.child = {}
def insert(self, word):
current = self.child
for l in word:
if l not in current:
current[l] = {}
current = current[l]
current['#']=1
def search(self, word):
current = self.child
for l in word:
if l not in current:
return False
current = current[l]
return '#' in current
def startsWith(self, prefix):
current = self.child
for l in prefix:
if l not in current:
return False
current = current[l]
return True
ob1 = Trie()
ob1.insert("apple")
print(ob1.search("apple"))
print(ob1.search("app"))
print(ob1.startsWith("app"))
ob1.insert("app")
print(ob1.search("app")) ইনপুট
ob1 = Trie()
ob1.insert("apple")
print(ob1.search("apple"))
print(ob1.search("app"))
print(ob1.startsWith("app"))
ob1.insert("app")
print(ob1.search("app")) আউটপুট
True False True True
