数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中两个字符串的删除操作
假设我们有两个单词 w1 和 w2，我们需要找到使 w1 和 w2 相同所需的最小步数，在每一步中，我们可以在任一字符串中删除一个字符。所以如果输入像“sea”和“eat”，那么输出将是 2，因为我们需要从 w1 中删除 's'，这将是“ea”，并从 w2 中删除“eat”中的“t”。然后它们就相同了。
为了解决这个问题，我们将遵循以下步骤
- n := s1 的大小，m := s2 的大小
- 在字符串 s1 和 s2 之前添加一个空格，然后相应地更新 s1 和 s2
- 创建一个大小为 (n + 1) x (m + 1) 的表格
- 对于 i := 1 到 m
- dp[0, i] := dp[0, i - 1] + 1
- 对于 i := 1 到 n
- dp[i, 0] := dp[i – 1, 0] + 1
- 对于 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 minDistance(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] + 1;
}
for(int i = 1; i <= n; i++){
dp[i][0] = dp[i - 1][0] + 1;
}
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] + 1, dp[i][j - 1] + 1);
}
}
}
return dp[n][m];
}
};
main(){
Solution ob;
vector<int> v = {1,1,1};
cout << (ob.minDistance("sea", "eat"));
}输入
"sea" "eat"
输出
2
更新于: 2020-04-29
239 次查看
广告