在C ++中编辑距离

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有两个单词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

    以上是 在C ++中编辑距离 的全部内容， 来源链接： utcz.com/z/338199.html

    回到顶部