編集距離アルゴリズム

アルゴリズム概要

編集距離（レーベンシュタイン距離）は、2つの文字列間での最小編集操作数を計算するアルゴリズムです。挿入・削除・置換の3つの操作を使用して、一つの文字列を別の文字列に変換するのに必要な最小回数を求めます。

基本概念の可視化

文字列1: "cat"

編集操作を適用

文字列2: "bat"

結果: 1回の操作

ソースコード解説

minDistance メソッド（標準版）

def minDistance(self, word1: str, word2: str) -> int:
    """
    編集距離 (Levenshtein Distance)
    Args:
        word1 (str): 最初の文字列
        word2 (str): 比較対象の文字列
    Returns:
        int: 最小編集距離
    """
    # 型検証
    if not isinstance(word1, str) or not isinstance(word2, str):
        raise TypeError("Both inputs must be strings")

    m, n = len(word1), len(word2)

    # 片方が空文字の場合
    if m == 0:
        return n
    if n == 0:
        return m

    # 空間最適化: 常に短い方を n にする
    if n > m:
        word1, word2 = word2, word1
        m, n = n, m

    # dp[j] = word1[0:i] と word2[0:j] の編集距離
    prev = list(range(n + 1))

    for i in range(1, m + 1):
        curr = [i] + [0] * n
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(
                    prev[j],      # 削除
                    curr[j - 1],  # 挿入
                    prev[j - 1]   # 置換
                )
        prev = curr

    return prev[n]

動的プログラミングの可視化

例: "cat" → "bat" の変換過程

上記のテーブルは動的プログラミングの各ステップを示します。各セルは、対応する部分文字列間の最小編集距離を表します。

処理ステップ詳細

1. 入力検証と初期化

2. エッジケースの処理

3. 空間最適化（短い文字列を選択）

4. DPテーブルの初期化

5. 二重ループによるDP計算

6. 最終結果の返却

計算量解析

時間計算量: O(m × n)

空間計算量: O(min(m, n))

最適化前の空間計算量: O(m × n)

この実装では、従来の2次元配列を使用したアプローチと比較して、空間計算量を大幅に削減しています。常に短い文字列をベースとして計算することで、メモリ使用量を最小化しています。

高速版実装

minDistance_fast メソッド（競技プログラミング向け）

def minDistance_fast(self, word1: str, word2: str) -> int:
    """
    競技プログラミング向け最適化版
    - 入力検証を省略
    - 空間 O(min(m, n))
    """
    if len(word2) > len(word1):
        word1, word2 = word2, word1

    m, n = len(word1), len(word2)
    prev = list(range(n + 1))

    for i in range(1, m + 1):
        curr = [i] + [0] * n
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
        prev = curr

    return prev[n]

高速版では型チェックを省略し、より簡潔な実装となっています。競技プログラミングなど、パフォーマンスが重視される場面で使用されます。