Edit Distance Algorithm Tutorial

Edit Distance measures the minimum number of single-character operations needed to transform one string into another. You have $3$ operations available:

$1.$ Insert a character $2.$ Delete a character $3.$ Replace a character with another

For example, transforming "kitten" to "sitting" requires $3$ operations: replace 'k' with 's', replace 'e' with 'i', and insert 'g' at the end.

You'll find Edit Distance everywhere: spell checkers suggest corrections, DNA sequencing aligns genetic strings, and fuzzy search matches similar queries.

I'll walk you through transforming "cat" to "cut".

Start with "cat". You compare characters from left to right. 'c' matches 'c', so no operation needed. 'a' doesn't match 'u', so you replace 'a' with 'u'. Now you have "cut". 't' matches 't'. Total cost: $1$ operation.

The key insight is optimal substructure. If you know the minimum edits for shorter prefixes, you can build the answer for longer strings. The best way to transform the first $i$ characters depends only on the best ways to transform smaller prefixes. This makes it perfect for dynamic programming.

You define $dp[i][j]$ as the minimum operations to transform the first $i$ characters of string $s$ into the first $j$ characters of string $t$.

Base cases:

• $dp[0][j] = j$ (insert $j$ characters to build $t$ from empty string)
• $dp[i][0] = i$ (delete $i$ characters to reach empty string)

Transition: When comparing $s[i-1]$ and $t[j-1]$:

If they match: $dp[i][j] = dp[i-1][j-1]$

If they don't match, take the minimum of:

• $dp[i-1][j] + 1$ (delete from $s$)
• $dp[i][j-1] + 1$ (insert into $s$)
• $dp[i-1][j-1] + 1$ (replace)

Here's the complete pseudocode:

function editDistance(s, t):
    m = length(s)
    n = length(t)
    dp = new array[m + 1][n + 1]
    
    for i from 0 to m:
        dp[i][0] = i
    for j from 0 to n:
        dp[0][j] = j
    
    for i from 1 to m:
        for j from 1 to n:
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],
                    dp[i][j - 1],
                    dp[i - 1][j - 1]
                )
    
    return dp[m][n]

Time complexity: $O(m \times n)$ where $m$ and $n$ are the lengths of the two strings. You fill every cell in the table exactly once.

Space complexity: $O(m \times n)$ for the full DP table.

Optimization: Since each row only depends on the previous row, you can reduce space to $O(\min(m, n))$ by keeping just $2$ rows and swapping them.

If you need to reconstruct the actual operations, you either keep the full table and backtrack, or store parent pointers. This brings space back to $O(m \times n)$.