Edit Distance
min(insert, delete, replace) = 1 + min(left, up, diagonal). Match copies the diagonal.
String 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.
Cost
- Best
- O(n * m)
- Average
- O(n * m)
- Worst
- O(n * m)
- Space
- O(min(n, m))
Before this
Taught by the same lesson
String DP covers these too, in the same run.