পাইথনে Trie (Prefix Tree) ইমপ্লিমেন্টেশন

মান করুন আমাদের Trie ডেটা স্ট্রাকচার বানাতে হবে, যেখানে তিনটি বেসিক অপারেশন থাকবে: insert(), search(), startsWith()। আমরা ধরে নিচ্ছি সকল ইনপুট লোয়ারকেস অক্ষরে। উদাহরণস্বরূপ, নিচের ফাংশন কল করলে:

• Trie trie = new Trie()
• trie.insert("apple")
• trie.search("apple")     // সত্য রিটার্ন করবে
• trie.search("app")       // মিথ্যা রিটার্ন করবে
• trie.startsWith("app")   // সত্য রিটার্ন করবে
• trie.insert("app")
• trie.search("app")       // সত্য রিটার্ন করবে

সমাধানের ধাপগুলো (ডিকশনারি ভিত্তিক):

• শুরুতে একটি খালি ডিকশনারি child বানান
• insert মেথড:
  • current := child
  • শব্দের প্রতিটি অক্ষর l এর জন্য:
    • যদি l current-এ না থাকে, তবে current[l] := নতুন ডিকশনারি
    • current := current[l]
  • current['#'] = 1 (শব্দের শেষ চিহ্নিত করতে)
• search মেথড:
  • current := child
  • শব্দের প্রতিটি অক্ষর l এর জন্য:
    • যদি l current-এ না থাকে, তবে মিথ্যা রিটার্ন করুন
    • current := current[l]
  • current['#'] == 1 হলে সত্য, অন্যথায় মিথ্যা রিটার্ন করুন
• startsWith মেথড:
  • current := child
  • প্রিফিক্সের প্রতিটি অক্ষর l এর জন্য:
    • যদি l current-এ না থাকে, তবে মিথ্যা রিটার্ন করুন
    • current := current[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