← Back to DSA Animator
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.