🎓 A1Learner
🔍

DSA Edit Distance

Edit distance is the smallest number of single-character changes that turns one string into another. A prefix table finds that number and one best sequence of changes.

The problem

Edit distance is the smallest number of single-character changes that turns one string into another. One change is an insertion, a deletion or a replacement of a single character.

The input is two strings. The output is one number. That number counts the cheapest possible sequence of changes.

The cases used in this article

cases = [
    ("kitten", "sitting", 3),
    ("flaw", "lawn", 2),
    ("cat", "cat", 0),
    ("", "abc", 3),
]
for a, b, expected in cases:
    print(repr(a), "->", repr(b), "distance:", expected)

The last row needs three insertions. Nothing exists to delete or replace. Each character of the target must arrive on its own.

Intuition: counting mismatched positions fails

The first idea walks both strings side by side. It counts the positions where the letters differ. That count works only when both strings keep the same length and alignment.

One insertion shifts every later letter. The positions then disagree everywhere. The true cost stays small, because one delete and one insert can fix the shift.

Position counting against flaw and lawn

a = "flaw"
b = "lawn"
mismatch = sum(1 for x, y in zip(a, b) if x != y)
print("positions that differ:", mismatch)
print("true distance: 2 (delete f, then insert n)")

Four positions differ. The distance is two. Position counting charges for the shift four times instead of fixing it once.

Brute force: try every first move

The brute force looks at the first characters of both strings. Equal first characters cost nothing and drop away. Different first characters force a choice among replace, delete and insert.

Each choice shortens at least one string. The search tries all three choices. It keeps the cheapest total it finds.

The recursive brute force, counted

calls = 0

def dist_brute(a, b):
    global calls
    calls += 1
    if not a:
        return len(b)
    if not b:
        return len(a)
    if a[0] == b[0]:
        return dist_brute(a[1:], b[1:])
    return 1 + min(
        dist_brute(a[1:], b[1:]),
        dist_brute(a[1:], b),
        dist_brute(a, b[1:]),
    )

for a, b in [("cat", "cut"), ("flaw", "lawn")]:
    calls = 0
    print(a, "->", b, "distance:", dist_brute(a, b), "calls:", calls)

The flaw and lawn search already makes 194 calls for two four-letter words. Many calls repeat the same pair of shorter strings. That repetition is the waste the table removes.

The optimal solution: a prefix table of cheapest costs

A prefix is a starting slice of a string. The state dp[i][j] holds the distance between the first i characters of one string and the first j characters of the other.

Equal last characters copy the diagonal cell for free. Different last characters add one to the cheapest of the diagonal, top and left cells. Each neighbour stands for one of the three moves.

The table on every case, with one edit script each

def edit_table(a, b):
    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
    for j in range(n + 1):
        dp[0][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], dp[i - 1][j], dp[i][j - 1])
    return dp

def script(a, b, dp):
    i, j = len(a), len(b)
    steps = []
    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:
            steps.append("replace " + a[i - 1] + " with " + b[j - 1])
            i, j = i - 1, j - 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            steps.append("delete " + a[i - 1])
            i -= 1
        else:
            steps.append("insert " + b[j - 1])
            j -= 1
    steps.reverse()
    return steps

cases = [("kitten", "sitting", 3), ("flaw", "lawn", 2), ("cat", "cat", 0), ("", "abc", 3)]
for a, b, expected in cases:
    dp = edit_table(a, b)
    result = dp[len(a)][len(b)]
    print(repr(a), "->", repr(b), "distance:", result, "expected:", expected, "match:", result == expected, "edits:", script(a, b, dp))

All four cases pass. Walking the finished table backwards also recovers one cheapest edit script. The distance and the script always agree in length.

Walkthrough: flaw becomes lawn

The walkthrough fills the table for flaw and lawn. The first row counts insertions into an empty string. The first column counts deletions down to an empty string.

Each inner cell then takes its value from its three neighbours. A match on the last characters copies the diagonal. A mismatch adds one to the cheapest neighbour.

The finished table for flaw and lawn

def edit_table(a, b):
    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
    for j in range(n + 1):
        dp[0][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], dp[i - 1][j], dp[i][j - 1])
    return dp

dp = edit_table("flaw", "lawn")
for row in dp:
    print(row)
print("bottom right cell:", dp[4][4])

The bottom right cell holds 2. One cheapest script deletes f at the start. It then inserts n at the end, and the middle three letters stay untouched.

Complexity

The table fills one cell per pair of prefixes, so its time is O(m times n) for string lengths m and n. The recursive search repeats the same subproblems, and its calls grow far faster than the cell count.

The table stores every cell, so its space is O(m times n). The script recovery needs the full table, which is why this article keeps every row.

Calls against cells at three sizes

calls = 0

def dist_brute(a, b):
    global calls
    calls += 1
    if not a:
        return len(b)
    if not b:
        return len(a)
    if a[0] == b[0]:
        return dist_brute(a[1:], b[1:])
    return 1 + min(dist_brute(a[1:], b[1:]), dist_brute(a[1:], b), dist_brute(a, b[1:]))

for a, b in [("ab", "cd"), ("abc", "def"), ("abcd", "efgh")]:
    calls = 0
    dist_brute(a, b)
    cells = (len(a) + 1) * (len(b) + 1)
    print("lengths", len(a), len(b), "- brute calls:", calls, " table cells:", cells)

The call count multiplies while the cell count only adds a row and a column at a time. Repeated subproblems explain the whole gap.

Edge cases and pitfalls

Turning a word into an empty string costs one deletion per character. Turning an empty string into a word costs one insertion per character. The border row and column carry exactly those counts.

The classic pitfall charges for a matching last character. A match copies the diagonal with no added cost. Adding one there inflates every distance that shares a suffix.

Edge cases, run

def edit_distance(a, b):
    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
    for j in range(n + 1):
        dp[0][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], dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

print("both empty:", edit_distance("", ""))
print("to empty:", edit_distance("abc", ""))
print("from empty:", edit_distance("", "abc"))
print("identical:", edit_distance("same", "same"))
print("all replaced:", edit_distance("abc", "def"))
print("one insertion:", edit_distance("cat", "cats"))

The all-replaced row costs three. One replacement per position beats any delete and insert pair. That check catches tables that price a replacement at two.

Exercise

The last characters of two prefixes differ. What does the new cell hold?