পাইথনে দীর্ঘতম প্যালিনড্রোমিক পরবর্তী দৈর্ঘ্য খুঁজে বের করার জন্য প্রোগ্রাম

ধরুন আমাদের একটি ছোট হাতের স্ট্রিং s আছে; আমাদের দীর্ঘতম প্যালিনড্রোমিক অনুসারীর দৈর্ঘ্য খুঁজে বের করতে হবে s.

সুতরাং, ইনপুট যদি s ="aolpeuvekyl" এর মত হয়, তাহলে আউটপুট হবে 5, যেমন প্যালিনড্রোম "লেভেল"।

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

• n :=s এর আকার
• একটি ফাংশন dp() সংজ্ঞায়িত করুন। এর জন্য i, j
লাগবে
• যদি i j এর মত হয়, তাহলে
  • প্রত্যাবর্তন 1
• অন্যথায় যখন i> j, তারপর
  • রিটার্ন 0
• অন্যথায়,
  • যদি s[i] s[j] এর মত হয়, তাহলে
    • রিটার্ন 2 + dp(i + 1, j - 1)
  • অন্যথায়,
    • সর্বাধিক dp(i + 1, j) এবং dp(i, j - 1) ফেরত দিন
• রিটার্ন dp(0, n - 1)

উদাহরণ (পাইথন)

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

class Solution:
   def solve(self, s):
      n = len(s)
      def dp(i, j):
         if i == j:
            return 1
         elif i > j:
            return 0
         else:
            if s[i] == s[j]:
               return 2 + dp(i + 1, j - 1)
            else:
               return max(dp(i + 1, j), dp(i, j - 1))
      return dp(0, n - 1)
ob = Solution()
s = "aolpeuvekyl"
print(ob.solve(s))

ইনপুট

"aolpeuvekyl"

আউটপুট

5