LeetCode 72 – Edit Distance | Love Me Some Coding

Edit Distance is the two-dimensional DP problem. If you only ever get one 2-D table fluent, make it this one — the recurrence, the table layout and the base cases all generalise directly to Longest Common Subsequence, Distinct Subsequences, Interleaving String and most of the string-DP family. It is also the problem where "what does dp[i][j] mean?" has to be answered precisely, because a vague definition makes the base cases unwritable.

The problem

Given two strings, return the minimum number of operations to convert the first into the second. The allowed operations are insert a character, delete a character, and replace a character.

"horse" -> "ros"     3     rorse (replace h) -> rose (delete r) -> ros (delete e)
"intention" -> "execution"  5
""      -> "abc"     3     three inserts
"abc"   -> ""        3     three deletes
"abc"   -> "abc"     0

State it precisely first

The definition that works:

dp[i][j] is the minimum number of operations to turn the first i characters of word1 into the first j characters of word2.

Note "first i characters", not "characters up to index i". The prefix length rather than the index is what makes i = 0 meaningful — the empty prefix — and the empty prefix is what gives you base cases without special pleading. The table is therefore (m+1) × (n+1), not m × n, and the extra row and column are the whole reason the code has no edge handling in it.

dp[0][j] = j      turning "" into j characters: j inserts
dp[i][0] = i      turning i characters into "": i deletes

The recurrence

Look at the last character of each prefix. If they match, they cost nothing and both can be dropped:

word1[i-1] == word2[j-1]   ->   dp[i][j] = dp[i-1][j-1]

Take the free match. There is never a reason to pay for an operation on two characters that are already equal — a formal exchange argument exists, but the intuition is enough to say out loud.

If they differ, one of the three operations must happen at this position, and each corresponds to one neighbour in the table:

dp[i][j] = 1 + min( dp[i-1][j-1],    replace word1[i-1] with word2[j-1]
                    dp[i-1][j],      delete word1[i-1]
                    dp[i][j-1] )     insert word2[j-1] into word1

              j-1     j
        i-1  [ ↖ ]  [ ↑ ]
        i    [ ← ]  [ ? ]

Getting delete and insert the right way round is the part people fumble. Reason from the definition rather than memorising: dp[i-1][j] means word1's prefix got one character shorter while word2's did not — a character of word1 was thrown away, so that is delete. dp[i][j-1] is the mirror image, so it is insert.

In practice it matters less than it feels like it should, because the two are symmetric and the min takes whichever is smaller. But being asked "which one is the insert?" and having to guess is a bad moment.

Java

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) dp[i][0] = i;    // i deletes
        for (int j = 0; j <= n; j++) dp[0][j] = j;    // j inserts

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];      // free -- take the match
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],              // replace
                                   Math.min(dp[i - 1][j], dp[i][j - 1]));  // delete, insert
                }
            }
        }

        return dp[m][n];
    }
}

charAt(i - 1) throughout, because dp[i] is about the first i characters and the last of those sits at index i - 1. Keeping that consistent is most of what makes a 2-D DP come out right the first time.

Python

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        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 word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j - 1],   # replace
                                       dp[i - 1][j],       # delete
                                       dp[i][j - 1])       # insert

        return dp[m][n]

Build the table with a comprehension, not [[0] * (n + 1)] * (m + 1). The second form makes m + 1 references to the same list, so writing dp[1][0] writes every row at once. It is the classic Python aliasing bug and it produces a table that looks plausible and is wrong.

Cutting the space to one row

Each cell reads only the row above and the cell to its left, so one row suffices — with one wrinkle. dp[i-1][j-1] is the value row[j] held before this iteration overwrote it, so it has to be saved:

        int[] row = new int[n + 1];
        for (int j = 0; j <= n; j++) row[j] = j;

        for (int i = 1; i <= m; i++) {
            int diagonal = row[0];        // dp[i-1][0], before it is clobbered
            row[0] = i;                   // dp[i][0]

            for (int j = 1; j <= n; j++) {
                int previousDiagonal = diagonal;
                diagonal = row[j];        // save dp[i-1][j] for the NEXT column

                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    row[j] = previousDiagonal;
                } else {
                    row[j] = 1 + Math.min(previousDiagonal, Math.min(row[j], row[j - 1]));
                }
            }
        }

Write the 2-D version first and this one second. It is genuinely harder to get right, and an interviewer would much rather see a correct table plus "I can reduce this to O(n) space by carrying the diagonal" than a broken clever version.

It also throws away exactly what you need to reconstruct the edit script, which is the standard follow-up. If they want the operations listed, keep the full table and walk backwards from dp[m][n], at each step moving to whichever neighbour the recurrence chose.

Complexity

Approach	Time	Space
Plain recursion	`O(3^(m+n))`	`O(m + n)` stack
Full table	`O(m · n)`	`O(m · n)`
One row	`O(m · n)`	`O(min(m, n))`

Roll the shorter string to get O(min(m, n)) — the distance is symmetric, so you may swap the arguments freely. That symmetry is worth one sentence: insert and delete are each other's inverses, so distance(a, b) == distance(b, a).

The pattern

Change what the recurrence does with a match and you get most of the family. Longest Common Subsequence (1143) takes 1 + dp[i-1][j-1] on a match and max of the two neighbours otherwise. Distinct Subsequences (115) sums instead of minimising. One Edit Distance (161) is this with an early exit once the budget of one is spent. Delete Operation for Two Strings (583) is Edit Distance without the replace, which is exactly LCS in disguise.

The shared skeleton — a (m+1) × (n+1) table, base cases on the empty prefixes, and a match/mismatch split — is the thing to internalise. The problems differ by two lines.

What the interviewer is checking

That you define dp[i][j] in words before writing any code.
The (m+1) × (n+1) table, and why the extra row and column remove the edge cases.
Base cases dp[i][0] = i and dp[0][j] = j.
That equal characters cost nothing and you take the diagonal.
That you can say which neighbour is insert and which is delete, from the definition.
Empty strings on either side.
The [[0] * n] * m aliasing trap in Python.
That you know the space can drop to one row, and why you wrote the table first.