在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)的桌子
对于我:=1到m
dp[0,i]:=dp[0,i-1]+1
对于我:=1到n
dp[i,0]:=dp[i–1,0]+1
对于我在1到n范围内
如果s1[i]=s2[j]
否则dp[i,j]=dp[i–1,j]+1和dp[i,j-1]+1的最小值
dp[i,j]:=dp[i–1,j-1]
对于1到m范围内的j
返回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