Edit Distance LeetCode 72 Guide

If you could master only one 2D dynamic programming problem, Edit Distance (#72) should be your pick. It is the problem that makes the entire string DP framework click — and once it clicks, you can apply the same skeleton to Longest Common Subsequence, Regular Expression Matching, Wildcard Matching, and a dozen more interview classics.

The edit distance leetcode problem asks a deceptively simple question: given two strings, what is the minimum number of single-character operations needed to transform one into the other? The three allowed operations — insert, delete, and replace — map directly to the three transitions in the recurrence. That clean mapping is what makes this problem such a powerful teaching tool.

In this walkthrough you will build the recurrence from scratch, fill the 2D DP table step by step, and then compress it down to a single row. By the end, you will have a reusable mental model for every string DP problem you encounter in interviews.

LeetCode 72 gives you two strings, word1 and word2. You need to find the minimum number of operations to convert word1 into word2. Each operation is one of three types: insert a character, delete a character, or replace a character.

For example, converting "horse" to "ros" takes three operations: replace "h" with "r" (rorse), remove "r" (rose), and remove "e" (ros). The minimum edit distance is 3.

The key insight is that you are comparing characters from both strings simultaneously. At any position (i, j) — where i is your index into word1 and j is your index into word2 — you either have a character match or you do not. That single branch drives the entire recurrence.

The recurrence for edit distance dp is elegant. Define dp[i][j] as the minimum number of operations to convert word1[0..i-1] into word2[0..j-1]. You compare the characters at positions i-1 and j-1, and then branch.

If the characters match — word1[i-1] equals word2[j-1] — no operation is needed. You simply carry the result forward: dp[i][j] = dp[i-1][j-1]. The cost of aligning the first i characters of word1 with the first j characters of word2 is the same as aligning one fewer character from each.

If the characters do not match, you have three choices. Insert a character into word1 to match word2[j-1], which costs 1 + dp[i][j-1]. Delete a character from word1, which costs 1 + dp[i-1][j]. Or replace word1[i-1] with word2[j-1], which costs 1 + dp[i-1][j-1]. You take the minimum of the three.

The 2D DP table has dimensions (m+1) by (n+1), where m is the length of word1 and n is the length of word2. The extra row and column handle the base cases: converting a string to or from an empty string.

Base cases are straightforward. dp[i][0] = i for all i, because converting the first i characters of word1 to an empty string requires i deletions. Similarly, dp[0][j] = j for all j, because building word2 from nothing requires j insertions.

You fill the table row by row, left to right. Each cell depends only on the cell above it (dp[i-1][j]), the cell to its left (dp[i][j-1]), and the cell diagonally above-left (dp[i-1][j-1]). This gives O(mn) time complexity and O(mn) space complexity.

Walk through the example of converting "horse" to "ros". The table starts with row 0 as [0, 1, 2, 3] and column 0 as [0, 1, 2, 3, 4, 5]. Fill each cell using the recurrence, and the bottom-right cell dp[5][3] gives the answer: 3.

Once you see that each cell only depends on the current row and the previous row, the optimization becomes clear. You do not need the full 2D table — two 1D arrays of length n+1 are sufficient. This reduces space from O(mn) to O(n).

You can push this further. Since you iterate left to right, the "previous row" values you need are the cell directly above (already in prev array) and the diagonal cell (which gets overwritten as you update). The trick is to save the diagonal value in a temporary variable before overwriting it.

For maximum savings, iterate over the shorter string in the inner loop. If m < n, swap the strings so that the inner loop runs over min(m, n) elements. This gives you O(min(m, n)) space while keeping O(mn) time.

Several edge cases simplify the problem. If either string is empty, the answer is the length of the other string — the base case handles this directly. If the strings are identical, every character matches and the answer is zero. If one string is a single character, the answer is either n-1 (if the character exists in word2 and you delete the rest) or a straightforward calculation from the base recurrence.

Edit Distance connects to a family of string DP problems that share the same 2D table structure. Longest Common Subsequence (#1143) uses the same diagonal-match idea but maximizes instead of minimizes. One Edit Distance (#161) is a restricted version where you check if exactly one operation suffices. Minimum ASCII Delete Sum (#712) replaces operation count with character-weighted costs.

Understanding the edit distance 2d dp framework also prepares you for Regular Expression Matching (#10) and Wildcard Matching (#44), where the recurrence branches on pattern characters rather than simple equality. The table structure and fill order are nearly identical.

The edit distance explained in this walkthrough follows a pattern you will see again and again: define a 2D table indexed by positions in two strings, set base cases for empty prefixes, compare characters at the current position, and branch on match versus no-match. That is the string DP framework.

Every string DP problem asks you to make the same three decisions. Do the current characters contribute to the answer (the diagonal move)? Can you skip a character from string 1 (move down)? Can you skip a character from string 2 (move right)? The costs and optimization criteria change, but the skeleton stays the same.

The levenshtein distance problem is also a favorite of interviewers because it tests multiple skills at once: defining recurrences, handling base cases, filling a table correctly, and optimizing space. If you can walk through this problem cleanly on a whiteboard, you demonstrate real DP fluency.

Practice this problem and its variants with YeetCode flashcards to build the muscle memory. When you see two strings and a minimization or maximization objective in an interview, your first instinct should be to sketch a 2D table — and Edit Distance is the problem that trains that instinct.