Approach Summary
dp[i][j] = min edits to convert word1[0..i) to word2[0..j). Match: dp[i-1][j-1]. Else: 1 + min(insert, delete, replace).
How to Recognize This Pattern
- Minimum operations to convert one string to another
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(m × n)
Tags
String DP