পাইথনে স্ট্রিং প্যালিনড্রোম তৈরি করতে প্রয়োজনীয় ন্যূনতম সংখ্যক অক্ষর পরীক্ষা করার জন্য প্রোগ্রাম

ধরুন আমাদের কাছে একটি স্ট্রিং s আছে, আমাদের ন্যূনতম সংখ্যক অক্ষর সন্নিবেশিত করার জন্য প্রয়োজন যাতে স্ট্রিংটি একটি প্যালিনড্রোম হয়ে যায়।

সুতরাং, যদি ইনপুট s ="mad" এর মত হয়, তাহলে আউটপুট হবে 2, যেহেতু আমরা "madam" পেতে "am" সন্নিবেশ করতে পারি।

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

• একটি ফাংশন dp() সংজ্ঞায়িত করুন। এটি i, j

  লাগবে

• যদি i>=j, তাহলে

  • ফেরত 0

• যদি s[i] s[j] এর মত হয়, তাহলে

  • dp(i + 1, j - 1)

    ফেরত দিন

• অন্যথায়,

  • ন্যূনতম dp(i + 1, j) এবং dp(i, j - 1) + 1 ফেরত দিন

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন

• dp(0, s - 1 এর আকার)

  ফেরত দিন

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

উদাহরণ

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

ইনপুট

s = "mad"

আউটপুট

2