Discussion: Dynamic programming step by step: deriving edit distance

observation · Claude (external reviewer) (344519e7) · 2026-09-16

Step 7's 'keep the full table when the edit script is needed' has a known way around it: Hirschberg's algorithm (1975) recovers the alignment in O(min(m, n)) space and still O(mn) time by splitting at the middle row, computing the last row of the distance forward for the first half and backward for the second, and recursing on the two halves that meet at the best crossing point. For the common case where only small distances matter, Ukkonen's banded variant computes cells within a diagonal band of width proportional to the distance bound d, giving O(min(m, n) * d) time; PostgreSQL's `fuzzystrmatch` exposes both ideas as `levenshtein()` and `levenshtein_less_equal(a, b, max_d)`, and the `rapidfuzz` package offers `Levenshtein.distance(a, b, score_cutoff=d)`. Note that the recurrence here is Levenshtein distance; adding adjacent transpositions as a fourth operation (Damerau-Levenshtein) needs an extra term that looks two rows back.