সমস্যা বিবরণ
একটি স্ট্রিং লিস্ট থেকে নির্দিষ্ট প্রিফিক্স দিয়ে শুরু হওয়া সব স্ট্রিং খুঁজে বের করতে হবে।
উদাহরণ
Input: List: ['tutorialspoint', 'tutorials', 'tutorialspython', 'python']
Prefix: 'tutorials'
Output: ['tutorialspoint', 'tutorials', 'tutorialspython']
pytrie মডিউল
pytrie হলো ট্রাই (Trie) ডেটা স্ট্রাকচারের পাইথন ইমপ্লিমেন্টেশন। প্রিফিক্স সার্চে খুব দক্ষ।
ইনস্টলেশন
pip install pytrie
কোড উদাহরণ
import pytrie
strings = ['tutorialspoint', 'tutorials', 'tutorialspython', 'python', 'learnpython']
prefix = 'tutorials'
# Trie তৈরি
trie = pytrie.StringTrie()
# সব স্ট্রিং ইনসার্ট
for item in strings:
trie[item] = item # key=value সমান
# প্রিফিক্স ম্যাচ
matched = trie.values(prefix)
print(list(matched))
# ['tutorials', 'tutorialspoint', 'tutorialspython']
pytrie-এর মূল মেথড
| মেথড | বর্ণনা |
|---|---|
trie[key] = value | ইনসার্ট/আপডেট |
trie[key] | এক্স্যাক্ট লুকআপ |
trie.values(prefix) | প্রিফিক্স ম্যাচ সব ভ্যালু |
trie.keys(prefix) | প্রিফিক্স ম্যাচ সব কী |
trie.items(prefix) | প্রিফিক্স ম্যাচ (key, value) |
del trie[key] | ডিলিট |
prefix in trie | প্রিফিক্স একজিস্ট চেক |
পারফরম্যান্স
- ইনসার্ট/সার্চ: O(L) — L = স্ট্রিং দৈর্ঘ্য
- প্রিফিক্স সার্চ: O(L + K) — K = ম্যাচ সংখ্যা
- হ্যাশ ম্যাপের চেয়ে প্রিফিক্স কোয়েরিতে অনেক দ্রুত
উপসংহার
- প্রিফিক্স-ভিত্তিক সার্চের জন্য
pytrieবেস্ট চয়েস - অটোকম্প্লিট, ডিকশনারি, আইপি রাউটিংয়ে ব্যবহার হয়
- পাইথন ডিকশনারি দিয়ে প্রিফিক্স সার্চ করা দুরুহ এবং স্লো
