পাইথনে দীর্ঘতম হ্রাসকারী শব্দ চেইনের দৈর্ঘ্য খুঁজে বের করার জন্য প্রোগ্রাম?

ধরুন আমাদের কাছে বৈধ শব্দের একটি তালিকা আছে, এবং একটি স্ট্রিং sও আছে, আমাদেরকে হ্রাস করা শব্দের দীর্ঘতম চেইনের দৈর্ঘ্য খুঁজে বের করতে হবে যা s থেকে শুরু করে এবং একক অক্ষরগুলি সরিয়ে দিয়ে তৈরি করা যেতে পারে এবং এখনও বৈধ শব্দ তৈরি করতে পারে৷

সুতরাং, যদি ইনপুটটি শব্দের মত হয় =["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"] s ="limit", তাহলে আউটপুট 4 হবে, যেহেতু আমরা "সীমা", "সীমা" ->"লিমি" -> "lii" -> "li" শব্দ থেকে শুরু করে চেইন তৈরি করতে পারি।

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

একটি ফাংশন সংজ্ঞায়িত করুন solve()। এর জন্য শব্দ লাগবে, s
সর্বোচ্চ_সংখ্যা :=0
প্রতিটি i শব্দে, কর
- যদি আমি s এর মত হয়, তাহলে
  - 0 থেকে s এর আকারের মধ্যে j এর জন্য, করুন
    - max_num :=সর্বাধিক 1 + সমাধান (শব্দ, s [সূচী 0 থেকে j-1] সংযুক্ত s [সূচী j + 1 থেকে শেষ পর্যন্ত]) এবং সর্বোচ্চ_সংখ্যা
রিটার্ন max_num

উদাহরণ

class Solution:
   def solve(self, words, s):
      max_num = 0
      for i in words:
         if i == s:
            for j in range(len(s)):
               max_num = max(1 + self.solve(words, s[:j] + s[j + 1 :]), max_num)
      return max_num

ob = Solution()
words = ["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"]
s = "limit"
print(ob.solve(words, s))

ইনপুট

["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"],"limit"