C++ 中两个字符串的删除操作
c++server side programmingprogramming更新于 2024/11/9 7:18:00
假设我们有两个单词 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) 的表格
- for i := 1 to m
- dp[0, i] := dp[0, i - 1] + 1
- for i := 1 to n
- dp[i, 0] := dp[i – 1, 0] + 1
- 对于范围在 1 到 n 内的 i
- 对于范围在 1 到 m 内的 j
- 如果 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]
- 对于范围在 1 到 m 内的 j
- return 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
