C ++中的有效Palindrome III
假设我们有一个字符串s和另一个数字k；我们必须检查给定的字符串是否为K回文。
如果字符串最多可以删除k个字符，则可以将其称为回文式。
因此，如果输入像s=“abcdeca”，k=2，则输出将为真，因为删除了'b'和'e'字符，这将是回文。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数lcs()，它将花费s，t，
n：=s的大小
在s之前添加一个空格
在t之前添加一个空格
定义一个大小为（n+1）x（n+1）的2D数组dp
对于初始化i：=1，当i<=n时，更新（将i增加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]的最大值
对于初始化j：=1，当j<=n时，更新（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