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