DSA AnimatorDSA animations
Edit Distance LC #72 Hard 2D DP
Problem

Given two strings word1 and word2, return the minimum number of operations (Insert, Delete, Replace) to convert word1 to word2.

Example 1
Input: "horse", "ros"
Output: 3
Example 2
Input: "abc", "abc"
Output: 0
dp[i][j] = min edits between w1[0..i-1] and w2[0..j-1]. Match→diag, Insert→left+1, Delete→up+1, Replace→diag+1.
Try Examples
Custom:
Approach
2D DP — dp[i][j] = min edits w1[0..i-1] → w2[0..j-1]
Match: dp[i-1][j-1]. Insert: dp[i][j-1]+1. Delete: dp[i-1][j]+1. Replace: dp[i-1][j-1]+1.
DP Table
Load an example to begin.
Variables
i, j
—
Match?
—
Picked
—
dp[i][j]
—
Step Logic
Press ▶ Play or Next Step to begin.
✏️
Ready
0 / 0
Select an example and press Play.
Algorithm
1
dp[i][j] = min edits w1[0..i-1] → w2[0..j-1]
2
Match: dp[i][j] = dp[i-1][j-1] (no cost)
3
Insert: dp[i][j-1]+1, Delete: dp[i-1][j]+1, Replace: dp[i-1][j-1]+1
4
Answer = dp[m][n]
Time
O(m×n)
Space
O(m×n)
Why This Works

Base: empty string needs length insertions/deletions. If chars match, copy diagonal. Else take min of insert (left+1), delete (up+1), replace (diag+1) — each operation costs 1.

How to solve Edit Distance

LeetCode 72 · Hard · Dynamic Programming · Pattern: 2D String DP

Why the obvious approach is slow

Trying every sequence of edits explodes quickly. The same prefix pairs appear in many sequences.

The key idea

Let dp of i and j be the edit distance between the first i characters of word one and the first j of word two. Turning a prefix into an empty string takes i deletions, so the first column is 0, 1, 2 and so on, and the first row likewise. If the characters match, no edit is needed, so copy the diagonal. Otherwise take 1 plus the smallest of three neighbours: above means delete, left means insert, and diagonal means replace. The bottom right cell is the answer.

Remember

Above is delete, left is insert, diagonal is replace. Matching characters are free.

Run the animation above on your own input, or watch the 1:55 video explanation of Edit Distance with a dry run and Java code.

More Dynamic Programming problems