C++で有効なパリンドロームIII

文字列sと別の数値kがあるとします。指定された文字列がK回文であるかどうかを確認する必要があります。

文字列から最大k文字を削除することで回文に変換できる場合、その文字列はK回文と呼ばれます。

したがって、入力がs ="abcdeca"、k =2のような場合、出力は「b」と「e」の文字を削除することで真になり、回文になります。

これを解決するには、次の手順に従います-

• 関数lcs（）を定義します。これにはs、t、

  が必要です。

• n：=sのサイズ

• sの前に1つの空白スペースを追加します

• tの前に1つの空白スペースを追加します

• サイズ（n + 1）x（n + 1）の2D配列dpを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のサイズでない場合は、-

  • trueを返す

• 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