程序以查找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