Canonical Deep-Dive: Edit Distance

Problem: Edit Distance (https://leetcode.com/problems/edit-distance/) The lesson: the five-step DP framework in two dimensions, where naming the two-index state is the entire battle.

This is a guided walk-through, not an answer key. It explains how to think through the five steps when the state needs two indices, and shows you the recurrence as a relation, the base cases, and the fill order in words. It stops short of an assembled, paste-runnable function on purpose. You write the actual Python yourself, in your own work repo. The tutor will not confirm your code; LeetCode’s judge will.

Restated: you are given two strings, word1 and word2. You may transform a string with three operations, each costing one: insert a character, delete a character, or replace a character with another. Return the minimum number of operations to turn word1 into word2. Either string may be empty.

Why this is 2-D, not 1-D

Last week, one index named the subproblem: a prefix, a step, an amount. Here, the subproblem is “how far apart are these two prefixes,” and that takes two numbers: how much of word1 you have consumed, and how much of word2. No single index captures it. The moment a problem compares two sequences position by position, that is the tell for a two-index state and a table instead of a row. Edit Distance is the cleanest example in the course, which is why it is the canonical.

The brute-force baseline

Before optimizing, have a baseline. The recursive brute force compares the strings from one end. Look at the last character of each remaining prefix. If they are equal, they cost nothing and you recurse on both prefixes shortened by one. If they differ, you try all three operations and take the cheapest: delete (shorten word1 by one), insert (shorten word2 by one), or replace (shorten both by one), each costing one plus the cost of the resulting subproblem.

  • Time: exponential. The same pair of prefixes gets recomputed through many different operation sequences.
  • Space: O(m + n) for the recursion stack depth.

The exponential cost comes entirely from recomputing the same (i, j) prefix pair over and over, and that repetition is the signal to memoize. That signal is the recognition cue for the whole week.

The five-step framework, in two dimensions

This is the same recipe as Week 13. Walk it in order, every time.

1. State. Define one quantity indexed by two numbers:

dp[i][j] is the edit distance between the first i characters of word1 and the first j characters of word2.

Say that sentence out loud before writing anything. Note carefully what i and j range over: they count characters, from 0 (the empty prefix) up to the full length. So the character that cell i is about lives at string index i - 1. Getting this off by one is the most common slip; pin it down now. If you can define the state cleanly, the rest follows. If you cannot, you do not yet understand the problem.

2. Transition (the recurrence). Compare the last character of each prefix, word1[i-1] and word2[j-1]. There are two cases.

The match case: the two characters are equal, so they pair off for free and you carry the answer for the two shorter prefixes diagonally.

The mismatch case: the characters differ, so you must spend one operation, and you take the cheapest of the three. Deleting word1’s last character leaves dp[i-1][j]. Inserting to match word2’s last character leaves dp[i][j-1]. Replacing word1’s last character with word2’s leaves dp[i-1][j-1]. As a relation:

if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]                                  # match: carry the diagonal, no cost
else:
    dp[i][j] = 1 + min( dp[i-1][j],      # delete from word1
                        dp[i][j-1],      # insert into word1
                        dp[i-1][j-1] )   # replace

That is the entire recurrence. The match case reads one neighbor (the diagonal); the mismatch case reads three (above, left, diagonal) and adds one. Notice this is a relation between cells, not assembled code: you still have to set up the table, seed the borders, and choose the loop order yourself.

3. Base cases. These are a whole row and a whole column, not a single cell, because either string can be empty.

dp[i][0] = i for every i: turning the first i characters of word1 into the empty string costs i deletions. dp[0][j] = j for every j: turning the empty string into the first j characters of word2 costs j insertions.

In particular dp[0][0] = 0: two empty strings are already equal. Seeding this border row and column correctly is half of getting the table right; a transition that reads into an unseeded border produces garbage.

4. Order of computation. The transition for dp[i][j] reads dp[i-1][j] (above), dp[i][j-1] (left), and dp[i-1][j-1] (up-left), all with smaller indices. So fill the table so those are already final: seed row 0 and column 0, then sweep i from 1 upward, and within each i sweep j from 1 upward. By the time you reach dp[i][j], every cell it reads is done. (The top-down equivalent is the same recurrence written as a recursive function with @lru_cache keyed on (i, j); memoization fills the same pairs on demand instead of in a sweep.)

5. Answer extraction. The answer is the single bottom-right cell:

dp[m][n], where m = len(word1) and n = len(word2).

That cell is the edit distance between the full word1 and the full word2, which is exactly what the problem asks for.

Walking the provided examples

  • word1 = "horse", word2 = "ros" gives 3. One optimal sequence: replace h with r (horse to rorse), delete r (rorse to rose), delete e (rose to ros). Three operations.
  • word1 = "intention", word2 = "execution" gives 5. The strings share a long run (ntion versus cution align in pieces), and five edits is the minimum; the table arrives at dp[9][9] = 5.
  • word1 = "", word2 = "abc" gives 3. This is a pure base-case read: the empty string needs three insertions, so dp[0][3] = 3. Worth tracing by hand precisely because it exercises the border, where off-by-one errors hide.

Trace the first one cell by cell at least once on paper. Watching the diagonal carry on a match and the 1 + min fire on a mismatch is what makes the recurrence stick.

The key insight, in one sentence

The edit distance between two prefixes is zero extra when their last characters match (carry the diagonal) and one plus the best of delete, insert, or replace when they do not; you compute every prefix pair once, smaller pairs first, and read the answer off the bottom-right corner. That reuse is what turns the exponential brute force into a single sweep over an (m + 1) by (n + 1) table.

Exact complexity

  • Time: O(m·n), where m = len(word1) and n = len(word2). There are (m + 1)(n + 1) cells, and each cell does O(1) work (one comparison, then a min over three cells). There is no hidden factor.
  • Space: O(m·n) for the full two-dimensional table.

The space optimization. Each row depends only on the row directly above it (dp[i-1][...]) and on the current row to the left (dp[i][j-1]). So you never need more than two rows at a time: a “previous” row and a “current” row, swapping them as i advances. That drops space to O(min(m, n)) if you orient the shorter string as the inner dimension so the rows are as short as possible. With more care you can update a single row in place, holding the one diagonal value you would otherwise overwrite. The time stays O(m·n) either way; only the memory shrinks. Mention this in your debrief; interviewers often ask for it as a follow-up.

Your work this week

  1. Implement Edit Distance yourself, bottom-up, in your own work repo (for example edit-distance.py). Build the (m + 1) by (n + 1) table with the correct initialization ([[0] * (n + 1) for _ in range(m + 1)], never the aliasing form), seed the border row and column, fill it row by row, and read dp[m][n]. Do not copy a solution; build it from the five steps above.
  2. Then write the top-down memoized version of the same recurrence (recursion on (i, j) plus @lru_cache). Confirm both give the same answers on the provided examples; convince yourself they are the same algorithm with different bookkeeping.
  3. Then write the two-row (or one-row) space-optimized version, and confirm it still matches. Run all of them against the provided examples in practice/-style local tests, then submit to LeetCode’s judge. Test the edge cases yourself: one empty string (answer is the other string’s length), two equal strings (answer 0), and two strings sharing no characters (answer is the longer length).
  4. Commit with a five-question debrief in the message. In answer 3, state the exact complexity above (O(m·n) time, O(m·n) space, reducible to O(min(m, n))) and why the table reduces to two rows.

When you can explain, from memory and with no AI open, the five steps for this problem (state, transition, base cases, order, answer), why the match case carries the diagonal while the mismatch case takes one plus the min of three neighbors, and how the table reduces to two rows, you own this problem. That explanation is exactly what an interviewer will ask for, and it is the template you will reuse on every 2-D DP problem this week.