পাইথনে একটি শব্দ বিন্যাসের দৈর্ঘ্যের দীর্ঘতম উপসর্গ ক্রম খুঁজে বের করার প্রোগ্রাম

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

সুতরাং, যদি ইনপুটটি w =["pqr", "pq", "m", "mn", "pqrs"] এর মত হয়, তাহলে আউটপুট হবে 3 কারণ আমরা ক্রমটি পেতে পারি:["pq", " pqr", "pqrs"], যার দৈর্ঘ্য 3।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• তালিকা সাজান w
• dp :=একটি মানচিত্র, যেখানে একটি কীর ডিফল্ট মান 0
• res :=0
• w এর প্রতিটি শব্দের জন্য করুন
  • dp[word] :=dp[দ্বিতীয় শেষ উপাদান পর্যন্ত শব্দের সাবস্ট্রিং] + 1
  • res :=res এর সর্বোচ্চ এবং dp[word]
• রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

from collections import defaultdict
def solve(w):
   w.sort()
   dp = defaultdict(int)
   res = 0
   for word in w:
      dp[word] = dp[word[:-1]] + 1
      res = max(res, dp[word])
   return res

w = ["pqr", "pq", "m", "mn", "pqrs"]
print(solve(w))

ইনপুট

["pqr", "pq", "m", "mn", "pqrs"]

আউটপুট

3