Pattern Recognition Drill
Medium 2-D Dynamic Programming
The Problem
Given two words, find the minimum number of operations (insert, delete, replace) to convert one to the other.
What approach would you use?
Think about it before scrolling down.
dp[i][j] = dp[i-1][j-1] if match, else 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]). O(mn).
1D optimization with prev variable. O(mn) time, O(n) space.
Common Trap
Don't forget the base cases: dp[i][0] = i (delete all), dp[0][j] = j (insert all).