বেশিরভাগ কে অক্ষর মুছে ফেলার পরে প্যালিনড্রোম তৈরি হতে পারে কিনা তা পরীক্ষা করার জন্য প্রোগ্রাম পাইথনে নয়

ধরুন আমাদের একটি স্ট্রিং s আছে, আমাদের পরীক্ষা করতে হবে যে আমরা বেশিরভাগ k অক্ষর মুছে ফেলার পরে এই স্ট্রিংটিকে প্যালিনড্রোম বানাতে পারি কি না।

সুতরাং, যদি ইনপুট s ="lieuvrel", k =4 এর মত হয়, তাহলে আউটপুট হবে True, আমরা প্যালিনড্রোম "লেভেল" পেতে তিনটি অক্ষর মুছে দিতে পারি।

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

• একটি ফাংশন lcs() সংজ্ঞায়িত করুন। এটি a, b
লাগবে
• m :=a এর আকার, n :=b এর আকার
• টেবিল :=আকারের ম্যাট্রিক্স (m + 1) x (n + 1) এবং 0 দিয়ে পূরণ করুন
• আমি 1 থেকে m রেঞ্জের জন্য, কর
  1 থেকে n রেঞ্জে j-এর জন্য
  • করুন
    • যদি a[i - 1] b[j - 1] এর মত হয়, তাহলে
      • টেবিল[i, j] :=1 + টেবিল[i - 1, j - 1]
    • অন্যথায়,
      • টেবিল[i, j] :=টেবিলের সর্বাধিক [i, j - 1] এবং টেবিল[i - 1, j]
• রিটার্ন টেবিল[m, n]
• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন:
• সত্য প্রত্যাবর্তন করুন যখন (s - lcs(s, s এর বিপরীত) <=k) অন্যথায় মিথ্যা

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

উদাহরণ

class Solution:
   def solve(self, s, k):
      def lcs(a, b):
         m, n = len(a), len(b)
         table = [[0] * (n + 1) for _ in range(m + 1)]
         for i in range(1, m + 1):
            for j in range(1, n + 1):
               if a[i - 1] == b[j - 1]:
                  table[i][j] = 1 + table[i - 1][j - 1]
               else:
                  table[i][j] = max(table[i][j - 1], table[i - 1][j])
         return table[m][n]

      return len(s) - lcs(s, s[::-1]) <= k
     
ob = Solution()
s = "lieuvrel"
k = 4
print(ob.solve(s, k))

ইনপুট

"lieuvrel", 4

আউটপুট

True