LeetCode 72 Edit Distance: The DP Table, Explained One Cell at a Time

Edit Distance is the problem that teaches "DP on two strings". It is LeetCode 72 (currently tagged Medium, previously listed as Hard), and it is the Levenshtein distance that powers spell checkers and fuzzy search. The code is short, but candidates often recite the recurrence without being able to explain which neighbour means insert and which means delete, or why the base row and column look the way they do. This guide derives the recurrence from a single question about the last character, fills the table visibly, and then optimises it.

The Problem: Minimum Operations to Convert One Word Into Another

Given word1 and word2, return the minimum number of operations to convert word1 into word2. Allowed operations, each costing 1:

• Insert a character
• Delete a character
• Replace a character

Constraints: both lengths up to 500, lowercase English letters. Examples from LeetCode:

Greedy does not work. You cannot decide locally whether a mismatch is best fixed by replacing, inserting or deleting, because each choice changes how the rest of the strings line up. That "choice changes the future alignment" structure, with lots of overlapping futures, is what makes it a DP problem.

Defining the Subproblem: Prefixes

The standard state for two-string DP is a pair of prefixes:

Why lengths rather than indices? Because the empty prefix (length 0) is a real and important case, and using lengths gives it index 0 cleanly. It is why the table is (m + 1) x (n + 1) and why you will see word1[i-1] in the code: the i-th character lives at index i − 1.

Base cases

• dp[0][j] = j: turning an empty string into the first j characters of word2 takes j inserts.
• dp[i][0] = i: turning the first i characters of word1 into an empty string takes i deletes.
• dp[0][0] = 0.

Deriving the Recurrence From the Last Character

Focus on the last characters: a = word1[i-1] and b = word2[j-1]. In any optimal edit script, one of a handful of things happens to them.

Case 1: a == b

Leave both alone and solve the rest: dp[i][j] = dp[i-1][j-1]. Matching characters cost nothing. (Why is keeping the match always optimal? See the FAQ: neighbouring cells differ by at most one, so the other options can never be cheaper.)

Case 2: a != b

Something must be spent on the end of the strings. Consider the three operations as what happens to make the last character of the result equal to b:

So:

if word1[i-1] == word2[j-1]:
    dp[i][j] = dp[i-1][j-1]
else:
    dp[i][j] = 1 + min(dp[i-1][j],     # delete word1[i-1]
                       dp[i][j-1],     # insert word2[j-1]
                       dp[i-1][j-1])   # replace word1[i-1] with word2[j-1]

A memory aid that works in interviews: up means you consumed a character of word1 without producing one of word2 (delete). Left means you produced a character of word2 without consuming one of word1 (insert). Diagonal consumes one of each (match or replace). If you think of the table as an alignment grid, every path from top-left to bottom-right is an edit script, and the DP finds the cheapest path.

Why the subproblems overlap

Cell (i-1, j-1) is reached from (i, j) directly via replace, and also via delete-then-insert or insert-then-delete. A naive recursion therefore recomputes the same prefixes over and over and blows up to roughly O(3^m+n). There are only (m+1)(n+1) distinct states, so caching them collapses the work to O(m·n).

Top-Down: Recursion With Memoization

Writing the recursion first is often the safest way to reach the right recurrence in an interview, and many interviewers accept memoization as a full solution.

from functools import lru_cache

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        @lru_cache(maxsize=None)
        def solve(i, j):          # convert word1[:i] into word2[:j]
            if i == 0:
                return j
            if j == 0:
                return i
            if word1[i - 1] == word2[j - 1]:
                return solve(i - 1, j - 1)
            return 1 + min(solve(i - 1, j),      # delete
                           solve(i, j - 1),      # insert
                           solve(i - 1, j - 1))  # replace
        return solve(len(word1), len(word2))

Recursion depth is at most m + n = 1,000 for LeetCode's limits, which is right at Python's default recursion limit of 1,000. It passes on LeetCode in practice, but if you run it locally with larger inputs, raise the limit or switch to bottom-up. Bottom-up also avoids function-call overhead, which matters for Python at 250,000 cells.

Filling the DP Table: horse → ros

Rows are prefixes of word1 = "horse", columns are prefixes of word2 = "ros". Fill the base row and column first, then go row by row, left to right. Each cell needs only its up, left and up-left neighbours, all already computed.

Selected cells, worked out:

1. dp[1][1] (h vs r). Mismatch. Up dp[0][1] = 1, left dp[1][0] = 1, diagonal dp[0][0] = 0. So 1 + 0 = 1: replace h with r.
2. dp[1][2] (h vs ro). Mismatch with o. Up dp[0][2] = 2, left dp[1][1] = 1, diagonal dp[0][1] = 1. 1 + 1 = 2.
3. dp[2][2] (ho vs ro). o == o, so copy the diagonal dp[1][1] = 1. "ho" to "ro" needs one replacement.
4. dp[2][3] (ho vs ros). o vs s mismatch. Up dp[1][3] = 3, left dp[2][2] = 1, diagonal dp[1][2] = 2. 1 + 1 = 2: insert s after converting "ho" to "ro".
5. dp[3][2] (hor vs ro). r vs o mismatch. Up dp[2][2] = 1, left dp[3][1] = 2, diagonal dp[2][1] = 2. 1 + 1 = 2: delete the r.
6. dp[4][3] (hors vs ros). s == s, copy diagonal dp[3][2] = 2.
7. dp[5][3] (horse vs ros). e vs s mismatch. Up dp[4][3] = 2, left dp[5][2] = 4, diagonal dp[4][2] = 3. 1 + 2 = 3: delete the e.

Two patterns are visible in the table. First, along any row or column adjacent cells differ by at most 1, which is what guarantees "take the diagonal on a match" is safe. Second, the answer is never below |m - n| (you must insert or delete at least the length difference) and never above max(m, n) (replace the overlapping part and insert or delete the rest). Here 2 ≤ 3 ≤ 5. Those bounds are a quick sanity check on any hand-computed answer.

Bottom-Up Edit Distance Code in Java, C++ and Python

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

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minDistance(const string& word1, const string& word2) {
        int m = word1.size(), n = word2.size();
        vector<vector<int>> dp(m + 1, vector<int>(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)
                dp[i][j] = (word1[i - 1] == word2[j - 1])
                    ? dp[i - 1][j - 1]
                    : 1 + min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]});
        return dp[m][n];
    }
};

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(m + 1):
            dp[i][0] = i
        for j in range(n + 1):
            dp[0][j] = j
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
        return dp[m][n]

Complexity: (m+1)(n+1) cells, O(1) each: O(m·n) time and space. For 500 × 500 that is about 250,000 cells, trivial in any language.

Recovering the Actual Edits by Backtracking

Interviewers sometimes ask "now print the operations". With the full table, walk back from (m, n) to (0, 0), at each step choosing the move that explains the current value.

def edit_script(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

    ops, i, j = [], m, n
    while i > 0 or j > 0:
        if i > 0 and j > 0 and word1[i - 1] == word2[j - 1]:
            i, j = i - 1, j - 1                       # match, free
        elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1:
            ops.append(f"replace {word1[i - 1]} at {i - 1} with {word2[j - 1]}")
            i, j = i - 1, j - 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            ops.append(f"delete {word1[i - 1]} at {i - 1}")
            i -= 1
        else:
            ops.append(f"insert {word2[j - 1]} at {i}")
            j -= 1
    return dp[m][n], ops[::-1]

# edit_script("horse", "ros")
# (3, ['replace h at 0 with r', 'delete r at 2', 'delete e at 4'])

Positions in this output refer to the original word1, which keeps them stable regardless of the order you apply them. When several moves tie, any of them gives an optimal script; the order of the elif branches just picks one.

Space Optimization: From O(m·n) to One Row

Row i depends only on row i - 1 and on cells to its left in row i. So two rows suffice. Better, one row plus a single saved variable suffices, because the only value you would overwrite before needing it is the diagonal.

Two rows

def min_distance_two_rows(word1, word2):
    m, n = len(word1), len(word2)
    prev = list(range(n + 1))
    for i in range(1, m + 1):
        cur = [i] + [0] * n
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
        prev = cur
    return prev[n]

One row with a saved diagonal

When you are about to overwrite dp[j], it still holds the "up" value (from row i − 1). dp[j-1] already holds the new "left" value. The old dp[j-1], the diagonal, was overwritten one step earlier, so stash it in a variable before each overwrite.

class Solution {
    public int minDistance(String word1, String word2) {
        // keep the row along the shorter word
        if (word2.length() > word1.length()) {
            String t = word1; word1 = word2; word2 = t;
        }
        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;             // dp[i][0]
            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;         // becomes dp[i-1][j-1] for the next j
            }
        }
        return dp[n];
    }
}

Swapping the words is valid because edit distance is symmetric: insert and delete mirror each other and replace is its own mirror. Space is O(min(m, n)). Time is still O(m·n).

If an interviewer asks for both low memory and the actual edits, Hirschberg's algorithm is the name to drop: it computes the optimal split point of word1 for the middle row of word2 using forward and backward single-row passes, then recurses on both halves. You will rarely be asked to code it.

Bounded edit distance

If you only need to know whether the distance is at most k (spell-check suggestions usually use k = 1 or 2), you only need cells within k of the diagonal, because any cell with |i - j| > k already costs more than k. That band reduces time to O(k · min(m, n)). It also gives a fast early exit when |m - n| > k.

Variants and Related Problems

The same prefix-pair table drives a family of string DPs. Changing the allowed operations or costs changes only the recurrence.

For a side-by-side treatment of LCS, edit distance and their cousins, see DP on strings: LCS and edit distance. If you want the general recipe for spotting DP and defining states, start with dynamic programming interview questions; LeetCode 139 Word Break is a good single-string DP to pair with this one.

Real-world uses worth mentioning

• Spell correction and search "did you mean". Candidates within edit distance 1 or 2 of the typed query, usually filtered by an index first (BK-trees, n-gram or deletion-based indexes) rather than compared against the entire dictionary.
• Fuzzy matching. Matching names, addresses or product titles with typos, for example deduplicating user-entered addresses on an e-commerce platform. Full-text engines such as Elasticsearch expose fuzzy queries based on Levenshtein distance (see Elasticsearch and inverted indexes).
• Bioinformatics. Sequence alignment algorithms such as Needleman-Wunsch are the same table with scoring matrices and gap penalties.
• Diff tools. Line-based diffs are built on the closely related LCS / shortest-edit-script problem.

How Edit Distance Shows Up in Interviews

Edit Distance is a staple at product companies, and it is a frequent second question in a DP-focused round. Interviewers watch for:

1. State definition first. Say "dp[i][j] is the cost to convert the first i characters into the first j" before writing any loop.
2. Justifying each transition. Map up, left and diagonal to delete, insert and replace, and say why a match takes the diagonal for free.
3. Base cases with meaning. "Empty to j characters is j inserts."
4. Fill order. Every dependency points up or left, so row-major order works.
5. Optimisation on request. One row with a saved diagonal; mention that you lose the ability to reconstruct the script.

Common mistakes

• Mixing up insert and delete directions. It does not change the numeric answer (both cost 1) but it breaks reconstruction and shows shaky understanding.
• Indexing word1[i] instead of word1[i-1] in a table indexed by length.
• Forgetting to set dp[0] to i at the start of each row in the one-row version.
• Overwriting the diagonal before using it in the one-row version.
• Assuming greedy works: matching the first equal characters you find can be far from optimal.

Follow-up questions

• "What if replace costs 2?" Then replace is never better than delete plus insert, and the answer becomes m + n - 2·LCS.
• "Can you check if the distance is at most 1 in O(n)?" Yes, LC 161: walk both strings until the first mismatch and compare the remainders.
• "How would you suggest corrections for a typed word against a 1 million word dictionary?" Do not compute edit distance against all of them; use an index to generate or filter candidates, then rank by distance and word frequency. This bridges into system design territory, like designing search autocomplete.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.