Memoization · 72 Edit Distance

Turn one word into another in the fewest edits

Given word1 and word2, find the minimum number of single-character inserts, deletes, and replaces to make them equal. The recursion is simple but explodes: the same sub-problem gets asked over and over. Memoization is what tames it.

The memoization idea → Recursion alone re-derives recur(i, j) from scratch every time it shows up, and it shows up an exponential number of times. Memoization is just recursion + a notebook: the first time you finish recur(i, j), you write the answer into memo[i][j]. Every later time that exact sub-problem is asked, you read it back instantly and skip the entire subtree underneath it. Each of the m×n cells gets computed once — exponential collapses to O(m·n). Watch the gold flashes below: those are the calls we didn't have to make.

memo table cell (i,j) = edit distance of the prefixes

not computed yet base case (∅ prefix) computed & cached cache hit (reused)

What's happening

Letters being compared

Call stack (deepest on the right)

Counters

Code

speed

Complexity: O(m·n) time and space — every cell computed once, then free lookups. · Naive recursion: ~O(3^(m+n)). · Same pattern powers Longest Common Subsequence (1143), Distinct Subsequences (115), Regular Expression Matching (10), and any "transform / align two sequences" problem.