69. Edit Distance

Define dp[i][j] = the minimum edits to transform word1[:i] into word2[:j] (the first i characters of word1 into the first j of word2). Two cases at each cell: the last characters match (free, copy from the diagonal), or they don't (we paid one op for either insert / delete / replace, take whichever is cheapest).

The recurrence

For i, j ≥ 1:

• If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] — no operation needed at this position; whatever we did to align the prefixes carries over.
• Otherwise: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]). The three cases correspond to:
  • dp[i-1][j-1] + 1 — replace word1[i-1] with word2[j-1].
  • dp[i-1][j] + 1 — delete word1[i-1].
  • dp[i][j-1] + 1 — insert word2[j-1].

Base cases: dp[0][j] = j (insert j chars to build word2[:j] from empty) and dp[i][0] = i (delete all i chars to reduce word1[:i] to empty).

Steps

1. Allocate dp of size (m+1) × (n+1).
2. Fill the first row and first column with 0..n and 0..m respectively.
3. For each i from 1 to m, for each j from 1 to n, fill dp[i][j] using the recurrence.
4. Return dp[m][n].

Walk-through

word1 = "horse", word2 = "ros". Expected answer: 3.

Walking the bottom-right back: from dp[5][3] = 3, the path could be:

1. Replace h → r (1 op).
2. Skip the o (match).
3. Delete r, delete s, then e→ wait, let's read the table more carefully. The standard path: horse → rorse (replace h→r) → rose (delete r) → ros (delete e). Three ops. ✓

Why three options always cover the case

Any single edit step transforms the source into something where the last char either isn't there (delete), is new (insert), or swapped (replace). After one such step, the remaining problem is a smaller dp cell — exactly the three transitions above.

Edge cases

• One word is empty: answer is the length of the other.
• Identical strings: zero ops; the diagonal stays at 0.

Complexity

• Time: O(m · n) — one pass to fill the table.
• Space: O(m · n) — the full table.

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;
        for (int j = 0; j <= n; j++) dp[0][j] = j;
        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];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
                                   Math.min(dp[i - 1][j], dp[i][j - 1]));
                }
            }
        }
        return dp[m][n];
    }
}

The 2D DP only ever reads from dp[i-1][...] (the row above) and dp[i][j-1] (the cell to the left). Keep just two rows around — the previous one and the one we're filling — and we drop space from O(m · n) to O(n).

Setup

We maintain two arrays of length n + 1:

• prev — the previous row, i.e. dp[i-1][...].
• curr — the row we're filling, i.e. dp[i][...].

After finishing each row, set prev = curr and continue.

Steps

1. Initialise prev = [0, 1, 2, ..., n] (the first row of the 2D table).
2. For i from 1 to m:
   • Start curr = [i] + [0] * n (first column is i).
   • For j from 1 to n:
     • If word1[i-1] == word2[j-1]: curr[j] = prev[j-1].
     • Else: curr[j] = 1 + min(prev[j-1], prev[j], curr[j-1]).
   • prev = curr.
3. Return prev[n].

Walk-through

word1 = "abc", word2 = "yabd".

prev starts: [0, 1, 2, 3, 4].

Row i = 1 (matching against 'a'):

prev after row 1: [1, 1, 1, 2, 3]. Continue similarly through rows 2, 3.

(Final answer for this example: 2 — replace c with d, insert y at front.)

Why we have to be careful with curr[j-1]

Look at the recurrence: curr[j] reads curr[j-1] (to its left) but prev[j-1] (diagonal up-left). If we walked j left-to-right and tried to overwrite prev in place, by the time we reach j we'd have already overwritten the value we needed for the diagonal. Two arrays avoid that.

Edge cases

• Same as the 2D version.
• Memory-constrained environments: this halves the memory footprint while preserving correctness and time.

Complexity

• Time: O(m · n).
• Space: O(n).