在C ++中制作字符串回文符的最少插入步骤

假设我们有一个字符串s，我们必须使这个字符串回文。在每个步骤中，我们都可以在任何位置插入任何字符，我们必须找到进行此回文的最低字符数。如果字符串像“ mad”，那么答案将是2，因为我们可以在“ mad”之前添加“ da”，或在“ mad”之后添加“ am”来创建此回文。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数lcs()，需要s，x：= s

• n：= s的大小

• 反转字符串x

• s：=连接s之前的空间，x：=连接x之前的空间

• 定义一个大小为（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]与x [j]相同，则-

• dp [i，j]：= dp [i，j]和dp [i – 1，j-1] + 1的最大值

• 对于初始化j：= 1，当j <= n时，更新（j增加1），-

• 返回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