数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序：查找两个字符串之间的最小编辑距离
假设我们有两个单词S和T，我们需要找到将S转换为T所需的最小操作数。
- 操作可以分为三种类型：
- 插入一个字符；
- 删除一个字符；
因此，如果输入字符串是“evaluate”和“fluctuate”，则结果为5。
为了解决这个问题，我们将遵循以下步骤：
n := s的长度，m := t的长度；
创建一个大小为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；
s := 在s前面添加一个空格，t := 在t前面添加一个空格；
对于i从1到n：
对于j从1到m：
如果s[i]不等于t[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 s, string t) {
int n = s.size();
int m =t.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;
}
}
s = " " + s;
t = " " + t;
for(int i =1;i<=n;i++){
for(int j = 1;j<=m;j++){
if(s[i] !=t[j]){
dp[i][j] = 1+min({dp[i-1][j],dp[i][j-1],dp[i-1][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年10月7日
410 次浏览
广告