C++で編集距離（レーベンシュタイン距離）を求めるアルゴリズム

問題の概要

2つの単語 word1 と word2 が与えられたとき、word1 を word2 に変換するために必要な最小の操作回数を求める問題です。使用できる操作は次の3種類です。

• 文字の挿入（insert）
• 文字の削除（delete）
• 文字の置換（replace）

例えば、入力が "evaluate" と "fluctuate" の場合、必要な最小の操作回数は 5 になります。

この問題は「編集距離（Edit Distance）」あるいは「レーベンシュタイン距離」と呼ばれる、動的計画法（DP）を用いて効率的に解ける有名な問題です。

解法のアルゴリズム

以下の手順に従って解くことができます。

1. n を w1 の長さ、m を w2 の長さとします。
2. (n+1) × (m+1) のサイズを持つ2次元配列 dp を作成します。
3. dp テーブルを初期化します。i = 0 のとき dp[i][j] = j（空文字列から j 文字を挿入する必要がある）、j = 0 のとき dp[i][j] = i（i 文字をすべて削除する必要がある）とします。
4. 比較を扱いやすくするため、w1 と w2 の先頭に空白文字を連結し、1始まりのインデックスとして処理します。
5. i を 1 から n まで、j を 1 から m まで動かしながら、次の遷移を行います。
   • w1[i] と w2[j] が異なる場合：dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])（削除・挿入・置換のいずれかを行う）
   • w1[i] と w2[j] が同じ場合：dp[i][j] = dp[i-1][j-1]（操作は不要）
6. 最後に dp[n][m] を返します。これが求める最小の操作回数です。

C++での実装例

理解を深めるために、以下の実装例を見てみましょう。

#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[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 テーブルの各セルを一度だけ計算するため、文字列の長さに対して効率的に動作します。