在C ++中编辑距离
为了解决这个问题,我们将遵循以下步骤-
n:=w1的大小,m:=w2的大小,
创建大小为n+1的数组dp
当我在0到n的范围内
dp[i,j]:=0
如果i=0,则dp[i,j]=j
否则,当j=0时,则dp[i,j]:=i
dp[i]:=大小为m+1的新数组
对于范围在0到m之间的j-
w1:=空格并连接w1,w2:=空格并连接w2
对于我在1到n范围内
如果w1[i]不是w2[j],则dp[i,j]:=1+dp[i–1,j],dp[i,j-1],dp[i–1,j的最小值–1]
否则dp[i,j]:=dp[i–1,j–1]
对于1到m范围内的j
返回dp[n,m]
示例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; class Solution { public: int minDistance(string w1, string w2) { int n = w1.size(); int m =w2.size(); int** dp = new int*[n+1]; for(int i =0;i<=n;i++){ dp[i] = new int[m+1]; for(int j=0;j<=m;j++){ dp[i][j]=0; if(i==0)dp[i][j]=j; else if(j==0)dp[i][j] = i; } } w1 = " " + w1; w2 = " " + w2; for(int i =1;i<=n;i++){ for(int j = 1;j<=m;j++){ if(w1[i] !=w2[j]){ dp[i][j] = 1+min({dp[i-1][j],dp[i][j-1],dp[i1][j-1]}); } else { dp[i][j] = dp[i-1][j-1]; } } } return dp[n][m]; } }; main(){ Solution ob; cout << (ob.minDistance("fluctuate", "evaluate")); }
输入值
"fluctuate" "evaluate"
输出结果
5