Dynamic Programming · LC #72
Edit Distance
`dp[i][j]` = minimum operations (insert, delete, replace) to convert `word1[0..i-1]` to `word2[0..j-1]`. Match → inherit diagonal; mismatch → 1 + min(replace, delete, insert).
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given two strings `word1` and `word2`, return the minimum number of operations (insert, delete, replace a character) to convert `word1` to `word2`.
Sample I/O
Input: word1="horse", word2="ros" Output: 3 (horse→rorse→rose→ros) Input: word1="intention", word2="execution" Output: 5
Intuition
How to Think About It
Intuition
Build a 2D table where dp[i][j] answers: "what's the cheapest way to align the first i characters of word1 with the first j characters of word2?" The three operations correspond to three adjacent cells in the table.
Core Concept
If `w1[i-1] == w2[j-1]`: `dp[i][j] = dp[i-1][j-1]` (free match). Else: `dp[i][j] = 1 + min(dp[i-1][j-1] // replace, dp[i-1][j] // delete from w1, dp[i][j-1] // insert into w1)`. Base: `dp[i][0] = i`, `dp[0][j] = j`.
When to use
Spell-checking, DNA sequence alignment, diff tools, fuzzy string matching, or any problem asking for minimum-cost string transformation.
When NOT to use
When only one operation type is allowed (simpler recurrence). When strings are very long and approximate solutions are acceptable (use heuristics). When you only need to check equality (use hashing).
Key Insights
What to Know Cold
- The three choices map geometrically: diagonal = replace/match, up = delete from w1, left = insert into w1.
- Base cases: converting empty string to j characters costs j insertions, and vice versa.
- Space can be reduced to O(n) using a rolling 1D array (only need previous row).
- When characters match, no operation is charged - `dp[i][j] = dp[i-1][j-1]` exactly, not `min(dp[i-1][j-1], ...)`.
- Edit distance is a metric: satisfies triangle inequality, useful for nearest-neighbour search in NLP.
1 example
Worked Examples
Convert "horse" to "ros" in 3 edits
horse → rorse (replace h→r) → rose (delete r) → ros (delete e).
2D DP table filled row by row; read answer at dp[m][n].
Output: 3
A top-5 DP problem at Google. Solving it fluently - including explaining the three transition directions - is a strong positive signal in senior engineering interviews.