পাইথনে কে-क্যারেক্টার ডিলিট করে প্যালিনড্রোম তৈরি করা সম্ভব কিনা চেক করার প্রোগ্রাম

ধরি আমাদের একটি স্ট্রিং s আছে, আমাদের চেক করতে হবে কি সর্বোচ্চ k ক্যারেক্টার ডিলিট করে এই স্ট্রিংকে প্যালিনড্রোম বানানো সম্ভব।

তাই, ইনপুট যদি s = "lieuvrel", k = 4 হয়, তবে আউটপুট হবে True, কারণ তিনটি ক্যারেক্টার ডিলিট করে "level" প্যালিনড্রোম পাওয়া যায়।

সমাধানের ধাপগুলো:

• lcs() ফাংশন ডিফাইন করুন। এটি a, b নিবে
• m := aর সাইজ, n := bর সাইজ
• table := (m+1) x (n+1) আকারের ম্যাট্রিক্স ০ দিয়ে ফিল করে
• i = ১ থেকে m পর্যন্ত, করুন
  • j = ১ থেকে n পর্যন্ত, করুন
    • যদি a[i-1] == b[j-1], তবে
      • table[i, j] := 1 + table[i-1, j-1]
    • অন্যথায়,
      • table[i, j] := max(table[i, j-1], table[i-1, j])
• table[m, n] রিটার্ন করুন
• মেইন মেথড থেকে করুন:
  • যদি len(s) - lcs(s, reverse(s)) <= k হয় তবে true রিটার্ন করুন, অন্যথায় false

বেশি বুঝতে নিচের বাস্তবায়নটি দেখুন:

উদাহরণ

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