Recursion & DP hard time O(m × n) space O(m × n)
DP — Edit Distance
Cell (i, j) holds the edit distance between the first i letters of one word and the first j of the other. If the letters match, nothing to do — carry the diagonal. Otherwise take the cheapest of insert, delete or replace and add one.
Turn "flaw" into "lawn" with as few edits as possible. Rows are "flaw", columns are "lawn".
1 / 19
A fixed scene — scrub through it, or open the code.
Practice
Machine twin: /dsa-viz-v2/edit-distance.json — the full deterministic run as structured data.