What is the brute force approach and complexity for Edit Distance?

Recurse on (i, j): a match is free, otherwise take the cheapest of three moves with time complexity O(3^(N + M)) and space complexity O(N + M).

What is the optimal approach and complexity for Edit Distance?

A cell reads only the row above and the cell to its left, so two rows are enough with optimal time complexity O(N · M) and space complexity O(M).

How do you identify the pattern for Edit Distance?

Look for key signals in the prompt: "fewest operations" indicates A minimum over several choices. The table keeps the cheapest value for each pair of prefixes.; "insert, delete or replace" indicates Three moves on the last letter, so each cell reads three cells. This is what makes it edit distance.; "turn word1 into word2" indicates Two strings, so the table has one axis for each string..

Edit Distance

Medium·LeetCode #72Basic Anchor

LeetCode

Jump:

30-Second Mental ModelDP — Strings, Edit distance (minimum of insert, delete, replace)

Complexity:O(3^(N + M))→O(N · M)

Key Insight

A cell reads the row above it and the cell to its left. So keep two rows: prev (row i − 1) and cur (row i). Fill cur from left to right, then swap the two. The last value of prev is the answer.

Core Validity Invariant

A cell is correct when its last letters are handled: a match copies the diagonal for free, and a mismatch pays 1 for the cheapest of insert, delete or replace.

Problem

You have two words, word1 and word2. Find the fewest operations that turn word1 into word2.

You may do three things to a word: insert one letter, delete one letter, or replace one letter with another. Each operation counts as 1, whatever letters are involved.

Input

Two strings word1 and word2. Either one can be empty.

Output

A single number: the fewest operations that turn word1 into word2.

Example 1

Input: word1 = "horse", word2 = "ros"

Output: 3

Replace h with r (rorse), delete r (rose), delete e (ros). No route uses only two operations.

Example 2

Input: word1 = "intention", word2 = "execution"

Output: 5

Delete t, replace i with e, replace n with x, replace n with c, and insert u. Five operations.

Constraints

• 0 ≤ word1.length, word2.length ≤ 500
• word1 and word2 consist of lowercase English letters.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If the last letters of the two words are the same, does that last letter need an operation at all?
2.
If the last letters differ, which of the three operations can fix them, and what does each one leave behind?
3.
After one operation, which smaller pair of words is left to solve? Is it shorter in word1, in word2, or both?
4.
How many operations turn an empty word into a word of 3 letters? How many turn a word of 3 letters into an empty word?
5.
Two words of length 5 and 3 share no letter at all. What is the fewest number of operations, without working it out letter by letter?

Brute force approach

Idea

Let ops(i, j) be the fewest operations for the first i letters of word1 and the first j letters of word2. If the last letters match, keep them for free: ops(i − 1, j − 1). Otherwise try all three moves and keep the cheapest, each plus 1: insert gives ops(i, j − 1), delete gives ops(i − 1, j), replace gives ops(i − 1, j − 1). An empty prefix costs the length of the other one.

Thinking process

1
Take word1 = "ab" and word2 = "ca". The full answer is ops(2, 2). The last letters are b and a. They differ, so try the three moves.
2
Insert: 1 + ops(2, 1). Delete: 1 + ops(1, 2). Replace: 1 + ops(1, 1). Each of these is another call of the same function on a smaller pair.
3
The base cases are ops(0, j) = j and ops(i, 0) = i. So ops(1, 0) = 1 and ops(0, 1) = 1, and ops(1, 1) = 1 + min(1, 1, 0) = 1, because a and c differ and the replace of a by c leaves two empty prefixes.
4
The same call comes back many times. In the tree for ab → ca, ops(0, 1) is worked out 3 times and ops(1, 1) 2 times. Brute force works each of those out again from the start.
5
The answer is ops(2, 2) = 2: replace a with c, then replace b with a.

Visual

Each circle is one call ops(i, j): the first i letters of word1 and the first j letters of word2. Edge labels are the operation that was chosen. Blue = the path from the root to the current call. Orange = a call already worked out on another branch; brute force works it out again.

Brute force: recursion on the two prefix lengthsword1 = "ab", word2 = "ca"step 1/20

calls

word1

▲i

word2

▲j

State

i (letters of word1): 2
j (letters of word2): 2
calls: 1
repeated calls: 0

compare b and a

Look at the last letters: b (word1) and a (word2).

Code & Implementation

brute.cpp

class Solution {
    // ops(i, j): fewest operations that turn the first i letters of word1 into the first j letters of word2.
    // Only the last letters decide the move: if they match, no cost; otherwise pay 1 for insert, delete or replace.
    int ops(const string& a, const string& b, int i, int j) {
        if (i == 0) return j;                          // word1 is used up: insert the j letters left in word2
        if (j == 0) return i;                          // word2 is used up: delete the i letters left in word1
        if (a[i - 1] == b[j - 1]) return ops(a, b, i - 1, j - 1);   // same last letter: keep it, no cost
        return 1 + min({ops(a, b, i, j - 1),           // insert b[j-1] after a[0..i)
                        ops(a, b, i - 1, j),           // delete a[i-1]
                        ops(a, b, i - 1, j - 1)});     // replace a[i-1] with b[j-1]
    }

public:
    int minDistance(string word1, string word2) {
        return ops(word1, word2, word1.size(), word2.size());
    }
};

Complexity

Time O(3^(N + M))Space O(N + M)

N is the length of word1 and M is the length of word2. Each call makes at most three calls and removes at least one letter, so there are at most 3^(N + M) calls. The space is the recursion depth, at most N + M.

Better approach

Why brute force is slow

Brute force makes the same call ops(i, j) from several branches of the recursion, and works it out again each time.

What repeated work are we doing?

In the tree for ab → ca, the call ops(0, 1) is worked out 3 times and ops(1, 1) 2 times. The calls below them are repeated as well.

What information can we reuse?

Each cell dp[i][j] is worked out once. It is then read by the cells to its right and below, so every value is computed a single time.

New approach

Idea

Make a table with one row for each prefix of word1 (plus the empty one) and one column for each prefix of word2. Fill each cell once, in order, from the cell to its left, above, and above-left. The last cell is the answer.

Thinking process

1
Row 0 and column 0 are the empty prefixes: dp[0][j] = j and dp[i][0] = i.
2
For horse → ros, the first row of letters is h. dp[1][1]: h and r differ, so 1 + min(dp[1][0], dp[0][1], dp[0][0]) = 1 + min(1, 1, 0) = 1. dp[1][2] = 1 + min(1, 2, 1) = 2. dp[1][3] = 1 + min(2, 3, 2) = 3.
3
Cell o, o (dp[2][2]): the letters match, so copy the cell above-left, dp[1][1] = 1.
4
Fill the rows in order. Each cell reads only cells that are already filled, so nothing is worked out twice.
5
The last cell dp[5][3] = 3 is the answer for horse → ros.

Code & Implementation

better.cpp

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        // dp[i][j] = fewest operations to turn word1's first i letters into word2's first j letters.
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        for (int i = 0; i <= n; i++) dp[i][0] = i;     // empty word2 prefix: delete all i letters
        for (int j = 0; j <= m; j++) dp[0][j] = j;     // empty word1 prefix: insert all j letters
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                if (word1[i - 1] == word2[j - 1]) dp[i][j] = dp[i - 1][j - 1];   // same letter: free
                else dp[i][j] = 1 + min({dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]});  // insert, delete or replace
            }
        return dp[n][m];
    }
};

Complexity

Time O(N · M)Space O(N · M)

The table has (N + 1) · (M + 1) cells, and each cell is one comparison and at most one min of three numbers. Keeping the whole table is what makes the space O(N · M).

Optimized approach

Idea

Start from brute force

Brute force recomputes ops(i, j) from many branches. Each value depends on only three smaller pairs of prefixes, so the whole problem is a table of pairs.

Find the repeated work

The same pair of prefixes is reached by several different sequences of moves, so its cost is worked out again each time. The table computes each pair once.

Define the state — what variables do I need?

dp[i][j]: The fewest operations to turn the first i letters of word1 into the first j letters of word2.
i, j: How many letters of each word are still in play. When i = 0 or j = 0, one word is used up.
dp[i − 1][j − 1], dp[i − 1][j], dp[i][j − 1]: The three smaller pairs the moves lead to: replace (or a free match), delete, and insert.

Define validity

A cell is correct when its last letters are handled: a match copies the diagonal for free, and a mismatch pays 1 for the cheapest of insert, delete or replace.

Define the transitions — when does each pointer move, and why is it safe?

Before the loops

dp[i][0] = i and dp[0][j] = j

With one word empty, the only way is to delete or insert every remaining letter.

word1[i − 1] = word2[j − 1]

dp[i][j] = dp[i − 1][j − 1]

Keeping the matching letters costs nothing, and it is never worse than the other two moves (see whyItWorks).

Every other cell

dp[i][j] = 1 + min(dp[i][j − 1], dp[i − 1][j], dp[i − 1][j − 1])

The last letter of word1 or word2 has to be handled by one of these three moves, so pay 1 for the cheapest.

What does the current window add to the answer?

Each cell holds the cheapest finish for its pair of prefixes, so the last cell dp[N][M] is the cost for the whole words.

Code & Implementation

optimal.cpp

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        // prev = row i-1 of the table, cur = row i. A cell only reads the row above it and the cell to its left,
        // so older rows can be thrown away.
        vector<int> prev(m + 1), cur(m + 1);
        for (int j = 0; j <= m; j++) prev[j] = j;      // row 0: insert j letters
        for (int i = 1; i <= n; i++) {
            cur[0] = i;                                // column 0: delete i letters
            for (int j = 1; j <= m; j++) {
                if (word1[i - 1] == word2[j - 1]) cur[j] = prev[j - 1];     // same letter: free, diagonal
                else cur[j] = 1 + min({cur[j - 1], prev[j], prev[j - 1]});  // insert, delete or replace
            }
            swap(prev, cur);                           // row i becomes the "row above" for the next i
        }
        return prev[m];                                // after the last swap, prev holds row n
    }
};

Complexity

Time O(N · M)Space O(M)

Each cell is still one comparison and one min, so the time is O(N · M). The code keeps two rows of M + 1 numbers, so the extra space is O(M).

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Recurse on (i, j): a match is free, otherwise take the cheapest of three moves	O(3^(N + M))	O(N + M)
Better	A table with one cell per pair of prefixes; each cell is filled once from three cells before it	O(N · M)	O(N · M)
Optimal	A cell reads only the row above and the cell to its left, so two rows are enough	O(N · M)	O(M)

Why does this belong to this pattern?

Clues in the problem statement

“fewest operations”A minimum over several choices. The table keeps the cheapest value for each pair of prefixes.
“insert, delete or replace”Three moves on the last letter, so each cell reads three cells. This is what makes it edit distance.
“turn word1 into word2”Two strings, so the table has one axis for each string.

Two strings+minimum over insert / delete / replace+each move costs 1→DP — Strings, Edit distance (minimum of insert, delete, replace)

This is the anchor of the sub-pattern. Each cell takes the cheapest of three moves on the last letters, and a match costs nothing. The next questions remove moves: Minimum ASCII Delete Sum keeps only the delete moves and weights each letter, and Interleaving String only asks whether each cell can be true. LCS looks similar, but it has no replace move, so it is not this table.

Don't make this mistake

Pattern confusion: n + m − 2 × LCS

✗ return word1.size() + word2.size() - 2 * lcs(word1, word2);

✓ dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]); // when the letters differ

LCS counts only insert and delete. A replace is one delete plus one insert there, so it costs 2, but it costs 1 here. On horse and ros the longest common subsequence has 2 letters (for example os), so n + m − 2 × LCS = 5 + 3 − 4 = 4. The real answer is 3: replace h with r, delete r, delete e.

Base cases set to 0

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

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

Turning an empty word1 into j letters takes j inserts, not 0. With the base at 0, horse → ros gives 2 instead of 3, and an empty word1 → ab gives 0 instead of 2.

Charging 1 for a match

✗ dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]); // always, even when the letters match

✓ if (word1[i-1] == word2[j-1]) dp[i][j] = dp[i-1][j-1]; else dp[i][j] = 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]);

Matching letters are kept for free. Charging 1 for them makes a → a cost 1 instead of 0.

Overwriting one row and losing the diagonal

✗ for (int j = 1; j <= m; j++) dp[j] = word1[i-1] == word2[j-1] ? dp[j-1] : 1 + min({dp[j-1], dp[j], dp[j-1]});

✓ Keep two rows (prev and cur), or save the old diagonal before it is overwritten.

When we reach column j, dp[j − 1] has already been overwritten with the new row. It is the cell to the left, not the cell above-left, so the diagonal is lost. On horse → ros this gives 6 instead of 3.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Strings translate into production architectures and low-level memory mechanics.

LLD Architecture