Blind Plus 100 Visualized

#93 · 2D DP

Edit Distance

Given two strings word1 and word2, return the minimum number of operations (insert a character, delete a character, replace a character) required to convert word1 into word2.

MediumLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

2D DP table over suffixes (or prefixes)

dp[i][j] is the edit distance between the suffix word1[i…] and the suffix word2[j…]. The first character decides everything: equal characters cost nothing; otherwise one operation (replace, delete or insert) leads to a smaller subproblem.

Memory layout

A (m + 1) × (n + 1) array of small integers, stored row by row.

OperationCost
timeO(m · n)
spaceO(m · n)

Rolling row

Each cell needs only the cell diagonally below-right, directly below and directly to the right, so a single row plus one saved diagonal value is enough.

Memory layout

One array of min(m, n) + 1 integers and two scalars.

OperationCost
spaceO(min(m, n))

Why it fits

  • The problem has optimal substructure: the best way to convert two suffixes only depends on the best way to convert shorter suffixes.
  • Many different operation sequences lead to the same pair of suffixes, so the number of distinct subproblems is just m · n; caching them turns exponential recursion into polynomial time.
  • All three operations have a simple recurrence meaning: replace = diagonal, delete = down, insert = right, which is exactly the 2D grid.

Why alternatives degrade

Greedy matching of equal characters:
Matching the first equal pair can force more operations later; the minimum needs all alternatives.
BFS over strings:
Each state is a whole string and the state space is exponential.
Longest common subsequence alone:
LCS ignores replacements; edit distance needs all three operations (it equals m + n − 2·LCS only when replace is not allowed).

Four approaches, from naive to production

1 · beginner

Plain recursion on the first characters

time O(3^(m+n))space O(m + n)

Compare the first characters. If equal, skip both. Otherwise take 1 plus the best of replace (skip both), delete (skip one of word1) and insert (skip one of word2). When one string is empty, the other's remaining length is the answer.

int minDistance(string word1, string word2) {
    function<int(int, int)> dist = [&](int i, int j) -> int {
        if (i == (int)word1.size()) return (int)word2.size() - j;
        if (j == (int)word2.size()) return (int)word1.size() - i;
        if (word1[i] == word2[j]) return dist(i + 1, j + 1);
        return 1 + min({dist(i + 1, j + 1), dist(i + 1, j), dist(i, j + 1)});
    };
    return dist(0, 0);
}

Flaws & bottlenecks

  • Three branches per mismatch: exponential time.
  • The same (i, j) pairs are recomputed many times.
  • Recursion depth up to m + n.

Interviewer cross-questions

Why can equal characters always be matched?

Say: Matching an equal pair never costs more than any alternative: skipping them would use at least one operation for no gain.

What do the three branches mean?

Say: dist(i+1, j+1) replaces word1[i] with word2[j], dist(i+1, j) deletes word1[i], dist(i, j+1) inserts word2[j] before word1[i].

How do you remove the repeated work?

Say: Cache the result of each (i, j) (memoisation) or fill a table bottom-up.

2 · intermediate

Memoised recursion

time O(m · n)space O(m · n)

Same recursion with a cache memo[i][j] checked before computing, so each of the m · n states is evaluated once.

int minDistance(string word1, string word2) {
    vector<vector<int>> memo(word1.size(), vector<int>(word2.size(), -1));
    function<int(int, int)> dist = [&](int i, int j) -> int {
        if (i == (int)word1.size()) return (int)word2.size() - j;
        if (j == (int)word2.size()) return (int)word1.size() - i;
        if (memo[i][j] != -1) return memo[i][j];
        int result;
        if (word1[i] == word2[j]) result = dist(i + 1, j + 1);
        else result = 1 + min({dist(i + 1, j + 1), dist(i + 1, j), dist(i, j + 1)});
        memo[i][j] = result;
        return result;
    };
    return dist(0, 0);
}

Flaws & bottlenecks

  • Recursion depth up to m + n can overflow the call stack for long strings.
  • Function-call overhead per state.
  • Still needs the full m × n cache.

Interviewer cross-questions

Why does the cache fix the complexity?

Say: There are only m · n distinct pairs (i, j), each computed once in O(1) given its neighbours.

Which cells does top-down compute?

Say: Only those reachable from (0, 0); here all are, but in general the cache may be sparser than the full table.

How do you avoid recursion?

Say: Fill the table iteratively from the base cases outward.

3 · advanced

Bottom-up table

time O(m · n)space O(m · n)

Fill dp from the bottom-right to the top-left. The last row and column are the borders (insert or delete the rest); inner cells copy the diagonal when characters match, or take 1 + min of the three neighbours.

int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = m; i >= 0; i--) {
        for (int j = n; j >= 0; j--) {
            if (i == m) dp[i][j] = n - j;
            else if (j == n) dp[i][j] = m - i;
            else if (word1[i] == word2[j]) dp[i][j] = dp[i + 1][j + 1];
            else dp[i][j] = 1 + min({dp[i + 1][j + 1], dp[i + 1][j], dp[i][j + 1]});
        }
    }
    return dp[0][0];
}

Flaws & bottlenecks

  • O(m · n) memory: 10⁸ cells for two 10⁴-character strings.
  • Computes cells that cannot influence the answer when strings are very different.
  • Gives only the distance; recovering the operations needs a backtrace.

Interviewer cross-questions

How do you recover the actual edit script?

Say: Walk from (0, 0): follow the neighbour whose value produced the cell (diagonal for equal or replace, down for delete, right for insert).

Why fill in reverse order?

Say: Each cell depends on cells with larger i or j, so they must already be filled.

Can the table be shrunk?

Say: Yes: only the row below and the current row are needed, and in fact one row plus one saved value.

4 · expert

Single rolling row, shorter string as columns

time O(m · n)space O(min(m, n))

Swap so word2 is the shorter string, keep one array of n + 1 numbers, and carry the old diagonal in a variable while sweeping the row right to left.

int minDistance(string word1, string word2) {
    if (word1.size() < word2.size()) swap(word1, word2);
    int m = word1.size(), n = word2.size();
    vector<int> row(n + 1);
    for (int j = 0; j <= n; j++) row[j] = n - j;
    for (int i = m - 1; i >= 0; i--) {
        int diag = row[n];
        row[n] = m - i;
        for (int j = n - 1; j >= 0; j--) {
            int saved = row[j];
            row[j] = word1[i] == word2[j] ? diag : 1 + min({diag, saved, row[j + 1]});
            diag = saved;
        }
    }
    return row[0];
}

Flaws & bottlenecks

  • Cannot reconstruct the edit script (the rest of the table is gone).
  • The diag / saved dance is easy to get wrong.
  • Hirschberg's divide and conquer is needed to get the script in linear space.

Interviewer cross-questions

Why is swapping safe?

Say: Edit distance is symmetric: an insertion into word1 is a deletion from word2, so the answer is the same either way.

Why save row[j] before overwriting?

Say: The old row[j] is the cell directly below, and it is also the next cell's diagonal; overwriting it first would lose that value.

What are the edge cases?

Say: One or both strings empty (the other's length), identical strings (0), and strings with no common letter (max(m, n)).

Synchronized code walkthrough

Showing: Plain recursion on the first characters — shares the player above; click any step to jump.

int minDistance(string word1, string word2) {
    function<int(int, int)> dist = [&](int i, int j) -> int {
        if (i == (int)word1.size()) return (int)word2.size() - j;
        if (j == (int)word2.size()) return (int)word1.size() - i;
        if (word1[i] == word2[j]) return dist(i + 1, j + 1);
        return 1 + min({dist(i + 1, j + 1), dist(i + 1, j), dist(i, j + 1)});
    };
    return dist(0, 0);
}