在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