A merchandising ticket asked for the cheapest way to turn the live SKU title into the new catalog name — insert a character, delete one, or replace one, each costing 1. The intern recursed on the three ops from every suffix pair. horse to ros returned 3. Two forty-character titles were still forking when the window closed.

Edit Distance asks for the minimum insert, delete, or replace count to turn word1 into word2. Each op costs 1. Recursing the three choices uses that spec and still pays an exponential tree.

This is an interview writeup, not a named-algorithm lecture. The edit distance post owns the costed grid, the empty-prefix init, and recovering one alignment. Here we only apply that fill to the prompt. LCS is the same family of prefix tables and a different job: longest shared subsequence, not cheapest edits.

The problem

Given two strings word1 and word2, return the minimum number of operations to convert word1 into word2. An operation is insert a character, delete a character, or replace a character. Each costs 1.

word1 = "horse",      word2 = "ros"        →  3
word1 = "intention",  word2 = "execution"  →  5
word1 = "same",       word2 = "same"       →  0

Note: Equal strings are already done — distance 0, no ops. Empty word1 is |word2| inserts; empty word2 is |word1| deletes. That is the first row and column, not a special case later.

Recursing on three ops is the honest brute force

From suffixes word1[i..] and word2[j..]: if the heads match, skip both. Otherwise try replace (advance both), delete (advance i), or insert (advance j). Exhausting one string costs the leftover length of the other. Correct. Exponential: overlapping prefix pairs repeat with no table.

int minDistanceRec(String word1, String word2) {
    return from(word1, word2, 0, 0);
}

int from(String a, String b, int i, int j) {
    if (i == a.length()) {
        return b.length() - j;
    }
    if (j == b.length()) {
        return a.length() - i;
    }
    if (a.charAt(i) == b.charAt(j)) {
        return from(a, b, i + 1, j + 1);
    }
    int replace = 1 + from(a, b, i + 1, j + 1);
    int delete = 1 + from(a, b, i + 1, j);
    int insert = 1 + from(a, b, i, j + 1);
    return Math.min(replace, Math.min(delete, insert));
}

At five-letter titles this is a rounding error. At production lengths you paid a fork tree for a question one cell per prefix pair answers: what is the cheapest way to turn this prefix of word1 into this prefix of word2?

Fill the grid: each cell from three neighbors

dp[i][j] is the min cost to turn word1[0..i) into word2[0..j). Seed dp[i][0] = i and dp[0][j] = j. Then each inner cell is the min of diagonal (match copies, mismatch +1), delete (+1 from above), insert (+1 from the left). The edit distance post is that recurrence. After the last cell, dp[n][m] is the answer.

Walk "horse" / "ros":

      ε  r  o  s
   ε  0  1  2  3
   h  1  1  2  3
   o  2  2  1  2
   r  3  2  2  2
   s  4  3  3  2
   e  5  4  4  3

dp[5][3] = 3

First row is inserts into empty word1. First column is deletes down to empty word2. dp[1][1] is h versus r: mismatch, substitute, 1. dp[2][2] is o versus o: match, copy 1. dp[4][3] is s versus s: match, copy 2. The last cell e versus s is a mismatch: 1 + min(delete 2, insert 4, substitute 3) = 3 — delete e. One script that spends those three: replace h with r, delete r, delete e.

The Java is that fill:

int minDistance(String word1, String word2) {
    int n = word1.length();
    int m = word2.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 0; i <= n; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= m; j++) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int matchOrSub = dp[i - 1][j - 1]
                    + (word1.charAt(i - 1) == word2.charAt(j - 1) ? 0 : 1);
            int delete = dp[i - 1][j] + 1;
            int insert = dp[i][j - 1] + 1;
            dp[i][j] = Math.min(matchOrSub, Math.min(delete, insert));
        }
    }
    return dp[n][m];
}

Time is O(n m) — one visit per prefix pair. Space is O(n m) for the table; two rolling rows of length m + 1 drop extra space to O(m) if they only want the integer.

Note: A match copies the diagonal; it does not skip the cell. Forgetting the 0 on a match charges a substitute you did not spend. LCS maximizes how much you keep. If substitute is forbidden, distance is |word1| + |word2| - 2 · LCS. Unit replace breaks that identity — one substitute can beat delete-plus-insert. Do not fill the LCS table on this board.

What interviewers usually poke next

  • Two rolling rows. You only read the previous row and the cell to the left. Same fill, O(min(n, m)) extra. Recovery of a script needs the full grid — that walk lives on the edit distance post; do not reconstruct it here unless they switch the prompt.
  • intention / execution. Same table, answer 5. You do not need to fill every cell out loud if they already watched horse / ros.
  • Empty strings. ("", "a") is 1. ("", "") is 0. The init already covers both.
  • Weighted ops. Affine gaps or a substitute that costs 2 change the numbers, not the shape. Name the costs at the method boundary and keep the same neighbors.
  • Damerau / adjacent transpose. A fourth operation. Spellcheck likes it. It is not this three-op min.

You are done with this problem when you can fill "horse" / "ros" to 3 on a whiteboard, say out loud why the three-op recursion is correct and why you do not need it, and point LCS tickets at the LCS table instead of this one.