在C ++中编辑距离

假设我们有两个单词word1和word2，我们必须找到从word1到word2进行协调所需的最小操作数。操作可以分为三种类型，分别是插入字符，删除字符和替换字符。因此，如果输入字符串为“求值”和“波动”，则结果将为5。

为了解决这个问题，我们将遵循以下步骤-

• n：= w1的大小，m：= w2的大小，

• 创建大小为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-

• w1：=空格并连接w1，w2：=空格并连接w2

• 对于我在1到n范围内

• 如果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]

• 对于1到m范围内的j

• 返回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