Hard · Two-Dimensional DP
Understand → Visualise → Practice.
The distance between two prefixes depends on deleting from the first, inserting into it, or replacing the final character.
If final characters match, use the diagonal state; otherwise take 1 plus min(delete, insert, replace).
dp[i][j] transforms a[:i] into b[:j].
Empty-to-prefix costs its length.
Match diagonally or pay one edit from three neighbours.
O(mn) time and O(n) space with rolling rows.
Insertion and deletion use different neighbours; draw the table before optimising its memory.
Read the full guide first: Dynamic Programming.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.