数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++实现两个字符串的最小ASCII删除和
假设我们有两个单词 w1 和 w2，我们需要找到使 w1 和 w2 相同的最小ASCII删除字符和，在每一步中，我们可以在任一字符串中删除一个字符。例如，输入是“sea”和“eat”，那么输出将是231，因为我们需要从 w1 中删除 's'，得到 “ea”，并从 w2 中删除 't'，得到 “ea”。然后它们相同。从“eat”中删除't' 会将116添加到总和中，最终两个字符串相同，115 + 116 = 231 是实现此目标的最小可能总和。
为了解决这个问题，我们将遵循以下步骤：
- n := s1 的大小，m := s2 的大小
- 在字符串 s1 和 s2 之前添加一个空格，然后相应地更新 s1 和 s2。
- 创建一个大小为 (n + 1) x (m + 1) 的表格。
- 对于 i := 1 到 m
- dp[0, i] := dp[0, i - 1] + s2[i]
- 对于 i := 1 到 n
- dp[i, 0] := dp[i – 1, 0] + s1[i]
- 对于 i 的范围从 1 到 n
- 对于 j 的范围从 1 到 m
- 如果 s1[i] = s2[j]
- dp[i, j] := dp[i – 1, j - 1]
- 否则 dp[i, j] = dp[i – 1, j] + 1 和 dp[i, j - 1] + 1 的最小值
- 如果 s1[i] = s2[j]
- 对于 j 的范围从 1 到 m
- 返回 dp[n, m]
示例(C++)
让我们看下面的实现来更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minimumDeleteSum(string s1, string s2) {
int n = s1.size();
int m = s2.size();
s1 = " " + s1;
s2 = " " + s2;
vector < vector <int> > dp(n + 1, vector <int>(m + 1));
for(int i = 1; i <= m; i++){
dp[0][i] = dp[0][i - 1] + s2[i];
}
for(int i = 1; i <= n; i++){
dp[i][0] = dp[i - 1][0] + s1[i];
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(s1[i] == s2[j]){
dp[i][j] = dp[i - 1][j - 1];
}
else{
dp[i][j] = min(dp[i - 1][j] + s1[i], dp[i][j - 1] + s2[j]);
}
}
}
return dp[n][m];
}
};
main(){
Solution ob;
cout << (ob.minimumDeleteSum("sea", "eat"));
}输入
"sea" "eat"
输出
231
更新于：2020年4月29日
393 次浏览
广告