AlgoScope

Edit Distance

min(insert, delete, replace) = 1 + min(left, up, diagonal). Match copies the diagonal.

Dynamic programming, algorithm, intermediateAlso called Levenshtein
Cell 1, 1 compares k with s and becomes 1.sittingkitten012345671123456
Cell 1, 1 compares k with s and becomes 1.sittingkitten012345671123456

String DP: kitten to sitting

Decision, step 2 of 44

(1, 1): 'k' against 's'. Different letters. Replace costs 1 + diagonal 0, delete 1 + above 1, insert 1 + left 1. Cheapest: 1.

How string dp works

Cost

Best
O(n * m)
Average
O(n * m)
Worst
O(n * m)
Space
O(min(n, m))

Taught by the same lesson

String DP covers these too, in the same run.