DP: Edit Distance (Levenshtein)

Edit distance (Levenshtein distance) is the minimum number of insertions, deletions and replacements that turn one string into another. It powers typo correction and fuzzy search.

Three operations

• insert a letter;
• delete a letter;
• replace a letter with another.

Each costs 1. For kitten to sitting the answer is 3: replace k with s, replace e with i, insert g.

State and transition

• State: dp[i][j] is the minimum number of operations turning the first i letters of a into the first j letters of b.
• Base: dp[i][0] = i (delete everything), dp[0][j] = j (insert everything).
• Same letter (a[i-1] == b[j-1]): dp[i][j] = dp[i-1][j-1].
• Otherwise: 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]), that is delete, insert or replace.
• Answer: dp[n][m].

def edit_table(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 i letters
    for j in range(m + 1):
        dp[0][j] = j                       # insert j letters
    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]            # same letter: free
            else:
                dp[i][j] = 1 + min(dp[i - 1][j],       # delete a[i-1]
                                   dp[i][j - 1],       # insert b[j-1]
                                   dp[i - 1][j - 1])   # replace
    return dp