数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中将字符串转换为回文串的最小插入步骤
假设我们有一个字符串 s，我们需要将其转换为回文串。在每一步中，我们可以在任何位置插入任何字符，我们需要找到使字符串成为回文串所需的最小字符数。如果字符串是“mad”，则答案将是 2，因为我们可以添加“da”到“mad”之前，或“am”到“mad”之后以使其成为回文串。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个函数 lcs()，它将接收 s，x := s
- n := s 的大小
- 反转字符串 x
- s := 在 s 前面连接空格，x := 在 x 前面连接空格
- 定义一个大小为 (n + 1) x (n + 1) 的二维数组 dp
- 初始化 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 的最大值
- 初始化 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
更新于: 2020-06-02
228 次查看
广告