C++で2つの文字列間の最小編集距離を見つけるプログラム

SとTの2つの単語があるとすると、SからTに変換するために必要な操作の最小数を見つける必要があります。操作には3つのタイプがあります。これらは

• 文字を挿入します
• 文字を削除する
• 文字を置き換えます。

したがって、入力文字列が「評価」および「変動」の場合、結果は5になります。

これを解決するには、次の手順に従います-

• n：=sのサイズ、m：=tのサイズ、

• サイズn+1の配列dpを作成します

• 0からnの範囲のiの場合

  • dp [i]：=サイズm+1の新しい配列

  • 0からmの範囲のjの場合：

    • dp [i、j]：=0

    • i =0の場合、dp [i、j] =j

    • それ以外の場合、j =0の場合、dp [i、j]：=i

• s：=空白スペースと連結s、t：=空白スペースと連結t

• 1からnの範囲のiの場合

  • 1からmの範囲のjの場合

    • 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