Edit Distance編輯距離

def edit_table(a, b):
    """dp[i][j]：把 a 的前 i 個字變成 b 的前 j 個字，最少要幾次插入、刪除或取代"""
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                               # 變成空字串：刪 i 次
    for j in range(n + 1):
        dp[0][j] = j                               # 從空字串變出來：插入 j 次
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]        # 最後一個字相同，不用動
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],   # 取代 a[i-1] → b[j-1]
                                   dp[i - 1][j],       # 刪除 a[i-1]
                                   dp[i][j - 1])       # 插入 b[j-1]
    return dp


def edit_script(a, b):
    """從右下角往回走，還原實際的操作（相同時優先取代，其次刪除，最後插入）"""
    dp = edit_table(a, b)
    i, j, ops = len(a), len(b), []
    while i > 0 or j > 0:
        if i > 0 and j > 0 and a[i - 1] == b[j - 1]:
            i, j = i - 1, j - 1                    # 相同，不算一步
        elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1:
            ops.append(f"取代 {a[i - 1]}→{b[j - 1]}")
            i, j = i - 1, j - 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            ops.append(f"刪除 {a[i - 1]}")
            i -= 1
        else:
            ops.append(f"插入 {b[j - 1]}")
            j -= 1
    return ops[::-1]


def edit_distance(a, b):
    """只要距離：滾動一列。cur[j] 用到的左上角就是 prev[j-1]"""
    prev = list(range(len(b) + 1))
    for i, ca in enumerate(a, 1):
        cur = [i] + [0] * len(b)
        for j, cb in enumerate(b, 1):
            cur[j] = prev[j - 1] if ca == cb else 1 + min(prev[j - 1], prev[j], cur[j - 1])
        prev = cur
    return prev[-1]


if __name__ == "__main__":
    print(edit_table("horse", "ros")[-1][-1], edit_script("horse", "ros"))
    # 3 ['取代 h→r', '刪除 r', '刪除 e']（和互動示範相同）
    print(edit_distance("intention", "execution"), edit_distance("recieve", "receive"))   # 5 2
    words = ["the", "ten", "tea", "eh", "tech", "then"]
    print(sorted(words, key=lambda w: (edit_distance("teh", w), w)))
    # ['eh', 'tea', 'tech', 'ten', 'the', 'then']：the 要 2 步，因為「兩個字對調」算兩次取代