ধরা যাক s নামে একটি স্ট্রিং এবং আরেকটি সংখ্যা k আছে; আমাদের চেক করতে হবে দেওয়া স্ট্রিংটি K-প্যালিনড্রোম কিনা।
একটি স্ট্রিংকে K-প্যালিনড্রোম বলা হয় যদি সেটি থেকে সর্বোচ্চ k ক্যারেক্টার রিমুভ করে প্যালিনড্রোমে রূপান্তর করা যায়।
তাই, যদি ইনপুট s = "abcdeca", k = 2 হয়, তবে আউটপুট হবে true কারণ 'b' এবং 'e' ক্যারেক্টার রিমুভ করলে এটি প্যালিনড্রোম হবে।
এটি সমাধান করতে, আমরা নিচের ধাপগুলো অনুসরণ করব -
একটি lcs() ফাংশন ডিফাইন করুন, এটি s, t নেবে,
n := s-এর আকার
s-এর আগে একটি ব্ল্যাঙ্ক স্পেস যোগ করুন
t-এর আগে একটি ব্ল্যাঙ্ক স্পেস যোগ করুন
আকার (n + 1) x (n + 1)-এর একটি 2D অ্যারে dp ডিফাইন করুন
i := 1 থেকে শুরু করুন, যখন i <= n, (i ১ করে বাড়ান), করুন -
j := 1 থেকে শুরু করুন, যখন j <= n, (j ১ করে বাড়ান), করুন -
dp[i, j] := dp[i - 1, j] এবং dp[i, j - 1]-এর ম্যাক্সিমাম
যদি s[i], t[j]-এর সমান হয়, তবে -
dp[i, j] := dp[i, j] এবং 1 + dp[i - 1, j - 1]-এর ম্যাক্সিমাম
dp[n, n] রিটার্ন করুন
মূল মেথড থেকে নিচের কাজগুলো করুন -
যদি s-এর আকার না থাকে, তবে -
true রিটার্ন করুন
x := ব্ল্যাঙ্ক স্পেস
i := s-এর আকার থেকে শুরু করুন, যখন i >= 0, (i ১ করে কমান), করুন -
x := x + s[i]
s-এর আকার রিটার্ন করুন
বेहतर বোঝার জন্য নিচের বাস্তবায়নটি দেখুন -
উদাহরণ
#include <bits/stdc++.h> using namespace std; class Solution { public: int lcs(string s, string t){ int n = s.size(); s = " " + s; t = " " + t; vector<vector<int> > dp(n + 1, vector<int>(n + 1)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); if (s[i] == t[j]) dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]); } } return dp[n][n]; } bool isValidPalindrome(string s, int k) { if (!s.size()) return true; string x = ""; for (int i = s.size() - 1; i >= 0; i--) x += s[i]; return s.size() - lcs(s, x) <= k; } }; main(){ Solution ob; cout << (ob.isValidPalindrome("abcdeca", 2)); }
ইনপুট
"abcdeca", 2
আউটপুট
1
