C++で2つの文字列間の最小編集距離（レーベンシュタイン距離）を求めるプログラム

2つの単語 S と T が与えられたとき、S を T に変換するために必要な最小の編集回数を求める問題を考えてみましょう。ここで使える操作は次の3種類です。

• 1文字を挿入する
• 1文字を削除する
• 1文字を置換する

この「最小編集距離」は、レーベンシュタイン距離とも呼ばれ、スペルチェッカや差分検出ツール、DNA配列の比較など、さまざまな分野で応用されている有名なアルゴリズムです。

たとえば、入力文字列が "evaluate" と "fluctuate" の場合、答えは 5 になります。

解き方のアプローチ：動的計画法（DP）

この問題は、動的計画法（Dynamic Programming）を使うことで効率的に解けます。dp[i][j] を「s の先頭 i 文字を t の先頭 j 文字に変換するのに必要な最小操作回数」と定義します。手順は以下のとおりです。

1. n := s の長さ、m := t の長さ とする
2. (n + 1) × (m + 1) のサイズの二次元配列 dp を作成する
3. i を 0 ～ n の範囲で繰り返す
   • dp[i] := サイズ m + 1 の新しい配列を作成
   • j を 0 ～ m の範囲で繰り返す
     • dp[i][j] := 0 で初期化
     • i = 0 のときは dp[i][j] = j（空文字列に j 文字挿入するため）
     • それ以外で j = 0 のときは dp[i][j] = i（i 文字すべて削除するため）
4. s と t の先頭に空白文字を連結する（インデックスを1始まりに揃えるため）
5. i を 1 ～ n、j を 1 ～ m の範囲で二重ループする
   • s[i] ≠ t[j] の場合：dp[i][j] := 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
     （削除・挿入・置換の3操作のうち最もコストの小さいものを選ぶ）
   • s[i] == t[j] の場合：dp[i][j] := dp[i-1][j-1]
     （文字が一致していれば追加の操作は不要）
6. 最後に dp[n][m] を返す

それでは、実際のC++での実装例を見てみましょう。

C++実装例

#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

計算量について

このアルゴリズムの時間計算量は O(n × m)、空間計算量も O(n × m) です。dp テーブル全体を保持していますが、直前の行だけを使う実装に工夫すれば、空間計算量を O(min(n, m)) まで削減することも可能です。