পাইথনে ওয়ার্ড অ্যারে-তে সর্বোচ্চ দৈর্ঘ্যের প্রিফিক্স সিকোয়েন্স খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি শব্দের তালিকা w আছে (সব লোয়ারকেস)। এমন সবচেয়ে লম্বা সিকোয়েন্স খুঁজে বের করতে হবে যেখানে প্রতিটি পূর্বের শব্দ পরবর্তী শব্দের প্রিফিক্স এবং পরবর্তী শব্দে শুধু একটি নতুন অক্ষর যোগ করা হয়েছে।

উদাহরণস্বরূপ, w = ["pqr", "pq", "m", "mn", "pqrs"] হলে আউটপুট হবে 3, কারণ সিকোয়েন্স: ["pq", "pqr", "pqrs"]।

সমাধানের পদ্ধতি

ডাইনামিক প্রোগ্রামিং (DP) এবং সর্টিং ব্যবহার করে সমাধান করা হয়।

1. শব্দগুলো লেক্সিকোগ্রাফিক্যালি সর্ট করুন।
2. dp ম্যাপ ব্যবহার করুন যেখানে dp[word] = word দিয়ে শেষ হওয়া সর্বোচ্চ সিকোয়েন্সের দৈর্ঘ্য।
3. প্রতিটি শব্দের জন্য, এর প্রিফিক্স (শেষ অক্ষর বাদে) খুঁজে dp[word] = dp[prefix] + 1 ক্যালকুলেট করুন।
4. সর্বোচ্চ মান ট্র্যাক করুন।

পাইথন কোড

from collections import defaultdict

def solve(w):
    w.sort()  # লেক্সিকোগ্রাফিক্যালি সর্ট করুন
    dp = defaultdict(int)
    res = 0
    
    for word in w:
        # word[:-1] = শেষ অক্ষর বাদে প্রিফিক্স
        dp[word] = dp[word[:-1]] + 1
        res = max(res, dp[word])
    
    return res

# টেস্ট
w = ["pqr", "pq", "m", "mn", "pqrs"]
print(solve(w))  # আউটপুট: 3

ব্যাখ্যা

সর্ট করার ফলে প্রিফিক্স শব্দগুলো আগে প্রক্রিয়া হয়। defaultdict(int) ডিফল্ট মান ০ দেয়, তাই নতুন শব্দের জন্য সিকোয়েন্স দৈর্ঘ্য ১ থেকে শুরু হয়।

সময় জটিলতা

O(n log n + n * k) - সর্টিং O(n log n), প্রতিটি শব্দ প্রক্রিয়া O(k) যেখানে k = গড় শব্দ দৈর্ঘ্য।