Edit Distance

MediumString DP · 2-D Table🧩 String DP LeetCode #72 ↗Updated Oct 30, 2026

Problem

You are given two strings word1 and word2. In one step you may insert a character, delete a character or replace a character of word1. Return the fewest steps needed to turn word1 into word2.

Inputword1 = "horse", word2 = "ros"Output3 (h→r, drop r, drop e)

Inputword1 = "intention", word2 = "execution"Output5

Inputword1 = "", word2 = "abc"Output3

0 ≤ word1.length, word2.length ≤ 500 · lowercase English letters only

Try it yourself

Java

class Solution {
    public int minDistance(String word1, String word2) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Only the last characters matter at each step: if they match, drop both for free; otherwise pay 1 for replace, delete or insert and recurse on a shorter prefix pair. There are just (m+1)×(n+1) prefix pairs, so a table kills the exponential blow-up.

PatternString DP

Instinct Two strings compared char by char (match, edit, interleave) means dp[i][j] over prefixes; one string's palindromes or splits means dp[l][r] or dp[i].

Memory hack Match? Go diagonal. Mismatch? Ask the neighbours. Up drops a char from s, left drops one from t, diagonal uses both.

Open the String DP guide →

Approaches

Brute ForcePlain Recursion on Prefixes

Time O(3^m+n)Space O(m+n)

Let solve(i, j) be the cost to turn the first i chars of word1 into the first j chars of word2. If one prefix is empty the answer is the other's length. Equal last chars cost nothing; otherwise try all three edits and keep the cheapest.

Java

public int minDistance(String word1, String word2) {
    return solve(word1, word2, word1.length(), word2.length());
}

private int solve(String a, String b, int i, int j) {
    if (i == 0) return j; // insert the rest of b
    if (j == 0) return i; // delete the rest of a
    if (a.charAt(i - 1) == b.charAt(j - 1)) return solve(a, b, i - 1, j - 1);
    int replace = solve(a, b, i - 1, j - 1);
    int delete = solve(a, b, i - 1, j);
    int insert = solve(a, b, i, j - 1);
    return 1 + Math.min(replace, Math.min(delete, insert));
}

Correct and shows the recurrence, but recomputes the same prefix pairs endlessly.

BetterBottom-Up 2-D Table

Time O(m·n)Space O(m·n)

Store dp[i][j] = answer for the two prefixes. Row 0 and column 0 are pure inserts/deletes. Every other cell reads its diagonal (replace / free match), the cell above (delete) and the cell to the left (insert).

Java

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

Polynomial and easy to trace, but keeps the whole grid in memory.

OptimalSingle Rolling Row

Time O(m·n)Space O(n)

Each row only needs the previous row, so keep one array. Before overwriting dp[j] it still holds the value above; the old dp[j-1] (saved in diag) is the diagonal, and the new dp[j-1] is the cell to the left.

Java

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[] dp = new int[n + 1];
    for (int j = 0; j <= n; j++) dp[j] = j;
    for (int i = 1; i <= m; i++) {
        int diag = dp[0]; // dp[i-1][0]
        dp[0] = i;
        for (int j = 1; j <= n; j++) {
            int up = dp[j]; // dp[i-1][j], about to be overwritten
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[j] = diag;
            } else {
                dp[j] = 1 + Math.min(diag, Math.min(up, dp[j - 1]));
            }
            diag = up;
        }
    }
    return dp[n];
}

Dry runword1 = "horse", word2 = "ros"

changed

row ""
0

1

2

3

vs "", r, ro, ros
+h
1

1

2

3

h→r replace
+o
2

2

1

2

o==o: take diag 1
+r
3

2

2

2

best ros = 2
+s
4

3

3

2

s==s: diag 2
+e
5

4

4

3

delete e → 3 ✔

Same time as the table with only one row of memory — the interview answer.

Pro tip

Swap the strings so the shorter one indexes the row to get O(min(m,n)) space.

At a glance

Level	Approach	Time	Space
Brute Force	Plain Recursion on Prefixes	`O(3^m+n)`	`O(m+n)`
Better	Bottom-Up 2-D Table	`O(m·n)`	`O(m·n)`
Optimal	Single Rolling Row	`O(m·n)`	`O(n)`

Common pitfalls

Mixing up which neighbour means insert vs delete — both cost 1, but name them right.
Forgetting the base row/column — turning a prefix into "" costs its length.
In the 1-D version, reading dp[j] after overwriting it — save up first.

Interview tips

Define the state out loud: cost to convert word1[0..i) into word2[0..j).
Draw the 3 arrows (diag, up, left) and map each to an operation.
Mention the row-rolling trick unprompted — it is the usual follow-up.

Pattern

Two-string prefix DP → when the answer for two strings depends only on shorter prefixes of both.

My notes saved in this browser