在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