C++で文字列回文を作成するための最小挿入手順

文字列sがあるとすると、この文字列回文を作成する必要があります。各ステップで、任意の位置に任意の文字を挿入できます。この回文を作成するために必要な最小数の文字を見つける必要があります。文字列が「mad」のような場合、「mad」の前に「da」を追加したり、「mad」の後に「am」を追加してこの回文を作成したりできるため、答えは2になります。

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

• 関数lcs（）を定義します。これにはs、x：=sが必要です
• n：=sのサイズ
• 文字列xを逆にします
• s：=sの前にスペースを連結し、x：=xの前にスペースを連結します
• サイズ（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]がx[j]と同じ場合、-
      • dp [i、j]：=最大dp [i、j]およびdp [i – 1、j-1] + 1
• return dp [n、n]
• メインメソッドからs– lcs（s）の戻りサイズ

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int lcs(string s){
      string x = s;
      int n = s.size();
      reverse(x.begin(), x.end());
      s = " " + s;
      x = " " + x;
      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] == x[j]){
               dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);
            }
         }
      }
      return dp[n][n];
   }
   int minInsertions(string s) {
      return s.size() - lcs(s);
   }
};
main(){
   Solution ob;
   cout << (ob.minInsertions("mad"));
}

入力

“mad”

出力

2