Edit Distance
min(insert, delete, replace) = 1 + min(left, up, diagonal); match copies the diagonal.
Decision · step 2 of 44String DP: kitten to sitting
(1, 1): 'k' against 's'. Different letters. Replace costs 1 + diagonal 0, delete 1 + above 1, insert 1 + left 1. Cheapest: 1.
What you will see
Three arrows into each cell; the operation chosen is labelled.
Cost
| Best | O(n * m) |
|---|---|
| Average | O(n * m) |
| Worst | O(n * m) |
| Space | O(min(n, m)) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next.
Screen readers: Table cells announce their state and value; each step announces which cells were read and the value written.
Reduced motion: Dependency arrows appear statically and the cell value crossfades.
Before this
Taught by the same lesson
String DP covers these too, in the same run.