数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中的编辑距离
假设我们有两个单词 word1 和 word2，我们需要找到将 word1 转换为 word2 所需的最少操作次数。操作可以是三种类型：插入一个字符、删除一个字符和替换一个字符。因此，如果输入字符串为“evaluate”和“fluctuate”，则结果将为 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
对于 i 的范围从 1 到 n
对于 j 的范围从 1 到 m
如果 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]
返回 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
更新于: 2020-05-26
389 次查看
广告