Edit Distance

def minDistance(word1: str, word2: str) -> int:
    """
    Edit Distance (Levenshtein Distance) の計算

    Args:
        word1: 変換元文字列
        word2: 変換先文字列

    Returns:
        最小編集距離

    Time Complexity: O(m*n)
    Space Complexity: O(m*n)
    """
    m, n = len(word1), len(word2)

    # エッジケース処理
    if m == 0:
        return n
    if n == 0:
        return m

    # DPテーブル初期化
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # ベースケース初期化
    for i in range(m + 1):
        dp[i][0] = i  # word1[0:i] -> "" の削除コスト
    for j in range(n + 1):
        dp[0][j] = j  # "" -> word2[0:j] の挿入コスト

    # DPテーブル構築
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                # 文字が一致する場合、コスト変化なし
                dp[i][j] = dp[i - 1][j - 1]
            else:
                # 3つの操作の最小コストを選択
                dp[i][j] = min(
                    dp[i - 1][j] + 1,      # 削除
                    dp[i][j - 1] + 1,      # 挿入
                    dp[i - 1][j - 1] + 1   # 置換
                )

    return dp[m][n]


# 使用例
if __name__ == "__main__":
    # Example 1: "horse" -> "ros"
    result1 = minDistance("horse", "ros")
    print(f"horse -> ros: {result1}")  # Output: 3

    # Example 2: "intention" -> "execution"
    result2 = minDistance("intention", "execution")
    print(f"intention -> execution: {result2}")  # Output: 5

def minDistance_optimized(word1: str, word2: str) -> int:
    """
    空間計算量最適化版 - O(min(m,n))
    """
    # 短い方を列、長い方を行にして空間効率化
    if len(word1) > len(word2):
        word1, word2 = word2, word1

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

    # 前の行と現在の行のみ保持
    prev_row = list(range(m + 1))
    curr_row = [0] * (m + 1)

    for i in range(1, n + 1):
        curr_row[0] = i

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

        # 行の入れ替え
        prev_row, curr_row = curr_row, prev_row

    return prev_row[m]