ধরুন আমাদের একটি স্ট্রিং s এবং আরেকটি সংখ্যা k; প্রদত্ত স্ট্রিংটি কে-প্যালিনড্রোম কিনা তা আমাদের পরীক্ষা করতে হবে।
একটি স্ট্রিংকে কে-প্যালিনড্রোম বলা হয় যদি এটি থেকে সর্বাধিক k অক্ষর সরিয়ে একটি প্যালিনড্রোমে রূপান্তরিত করা যায়।
সুতরাং, যদি ইনপুটটি s ="abcdeca", k =2 এর মত হয়, তাহলে আউটপুট সত্য হবে যেমন 'b' এবং 'e' অক্ষর মুছে দিলে তা হবে প্যালিনড্রোম।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন lcs() সংজ্ঞায়িত করুন, এটি s, t,
লাগবে -
n :=s
এর আকার -
s
এর আগে একটি ফাঁকা স্থান যোগ করুন -
t
এর আগে একটি ফাঁকা স্থান যোগ করুন -
একটি 2D অ্যারে ডিপি আকারের (n + 1) x (n + 1) সংজ্ঞায়িত করুন
-
আরম্ভ করার জন্য i :=1, যখন i <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), −
-
j শুরু করার জন্য :=1, যখন j <=n, আপডেট করুন (j 1 দ্বারা বৃদ্ধি করুন), করুন −
-
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 এর আকার না হয়, তাহলে −
-
প্রত্যাবর্তন সত্য
-
-
x :=ফাঁকা স্থান
-
আরম্ভ করার জন্য i :=s এর আকার, যখন i>=0, আপডেট করুন (i 1 দ্বারা কম করুন), −
-
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
