मान लीजिए हमारे पास एक स्ट्रिंग s और दूसरी संख्या k है; हमें यह जांचना होगा कि दी गई स्ट्रिंग के-पैलिंड्रोम है या नहीं।
एक स्ट्रिंग को के-पैलिंड्रोम कहा जाता है यदि इसे से अधिकतम k वर्णों को हटाकर इसे पैलिंड्रोम में बदला जा सकता है।
इसलिए, यदि इनपुट s ="abcdeca", k =2 जैसा है, तो आउटपुट सत्य होगा जैसे 'b' और 'e' वर्णों को हटाकर, यह पैलिंड्रोम होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन lcs() को परिभाषित करें, इसमें s, t,
. लगेगा -
n :=s का आकार
-
s से पहले एक खाली जगह जोड़ें
-
t से पहले एक खाली जगह जोड़ें
-
एक 2D सरणी dp आकार (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]
-
-
-
-
वापसी डीपी [एन, एन]
-
मुख्य विधि से निम्न कार्य करें -
-
यदि 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