LeetCode 72 ·
Hard
Edit Distance
Find the minimum number of single-character edits to turn word1 into word2.
Try it
Step through the core mechanic. The simulator below runs the advanced dp shape this problem is built on.
Walk the pattern
No dedicated step-through for this one yet. The shape is Advanced DP — its pattern page has the interactive walkthrough, the reference implementation, and a five-problem progression that this problem sits inside.
The approach
dp[i][j] = edits between prefixes. If characters match, carry dp[i−1][j−1]; else 1 + min(insert, delete, replace) = 1 + min(dp[i][j−1], dp[i−1][j], dp[i−1][j−1]).
| Aspect | Value |
|---|---|
| Pattern | Advanced DP |
| Recognise it by | Min insert/delete/replace to convert one string to another. |
| Time complexity | O(mn) |
| Space complexity | O(mn) |
| Difficulty | Hard |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.