程序以查找C ++中两个字符串之间的最小编辑距离
假设我们有两个词S和T，我们必须找到从S转换为T所需的最小操作数。这些操作可以是三种类型，分别是
插入一个字符，
删除字符
替换字符。
因此，如果输入字符串为“求值”和“波动”，则结果将为5。
为了解决这个问题，我们将遵循以下步骤-
n：=s的大小，m：=t的大小，
创建大小为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：
s：=空白并连接s，t：=空白并连接t
对于我在1到n范围内
如果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]
对于1到m范围内的j
返回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