C++ 中的编辑距离
c++server side programmingprogramming更新于 2024/11/7 22:11:00
假设我们有两个单词 word1 和 word2，我们必须找到从 word1 到 word2 所需的最少操作数。操作可以分为三种类型，即插入字符、删除字符和替换字符。因此，如果输入字符串是"求值"并且"波动"，则结果将为 5。
为了解决这个问题，我们将遵循以下步骤 −
n := w1 的大小，m := w2 的大小，
创建一个大小为 n + 1 的数组 dp
对于 i 在 0 到 n 的范围内
dp[i] := 大小为 m + 1 的新数组
对于 j 在 0 到 m 的范围内 −
dp[i, j] := 0
如果 i = 0，则 dp[i,j] = j
否则当 j = 0，则 dp[i, j] := i
w1 := 空格并连接 w1，w2 := 空格并连接 w2
对于范围为 1 到 n 的 i
对于范围为 1 到 m 的 j
如果 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]
return 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
