পাইথনে স্ট্রিং প্যালিনড্রোম বানাতে ন্যূনতম ক্যারেক্টার ইনসার্ট করার প্রোগ্রাম

মান ল করুন একটি s স্ট্রিং, আমাদের ন্যূনতম কতটি ক্যারেক্টার ইনসার্ট করলে স্ট্রিংটি প্যালিনড্রোম হবে তা খুঁজে বের করতে হবে।

যদি ইনপুট হয় s = "mad", তবে আউটপুট হবে ২, কারণ "am" ইনসার্ট করলে "madam" পাওয়া যায়।

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:

একটি dp() ফাংশন সংজ্ঞায়িত করুন। এটি i, j গ্রহণ করবে।
যদি i >= j, ০ ফেরত দিন।
যদি s[i] == s[j], dp(i+1, j-1) ফেরত দিন।
অন্যথায়, min(dp(i+1, j), dp(i, j-1)) + 1 ফেরত দিন।
মূল মেথড থেকে: dp(0, len(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"