ZERO / HERO
Cheapest way to retype a word

Edit Distance

The analogy

How few single-character edits turn "kitten" into "sitting"? At each cell you consider three moves — replace a letter, delete one, or insert one — and take whichever is cheapest, building on answers you already have.

Visualizer

Three ways to fix a letter

step 1 / 8
øsitting
ø01234567
k
i
t
t
e
n

Turn "kitten" into "sitting" in as few single-character edits as possible.dp[i][j] = edits to turn first i of A into first j of B

def edit_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1): dp[i][0] = i      # delete all
    for j in range(m + 1): dp[0][j] = j      # insert all

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]      # free
            else:
                dp[i][j] = 1 + min(
                    dp[i-1][j-1],            # replace
                    dp[i-1][j],              # delete
                    dp[i][j-1])              # insert
    return dp[n][m]

edit_distance("kitten", "sitting")   # 3

# Damerau adds transposition:
#   if a[i-1]==b[j-2] and a[i-2]==b[j-1]:
#       dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1)
Check yourself

Which three operations does the min() in Levenshtein correspond to?