Hints — p60 Edit Distance

Hint 1. Three operations (insert, delete, substitute), each cost 1. Think recursively on prefixes: f(i, j) = edit distance between word1[:i] and word2[:j].

Hint 2. If the last characters match, no op needed: f(i, j) = f(i-1, j-1). Otherwise, try all three operations on the last position and take the minimum, paying +1 for the op.

Hint 3. f(i, j) = 1 + min(f(i-1, j-1) [sub], f(i-1, j) [del], f(i, j-1) [ins]). Memoize → 2D DP table. O(m·n).

Hint 4. Base cases are NOT zeros: dp[i][0] = i (delete i chars), dp[0][j] = j (insert j chars). Forgetting these silently breaks everything.

Hint 5. Space compress to 1D with a prev_diag saved value (same trick as LCS). To recover the actual edit script, keep the full table and backtrack from dp[m][n], picking whichever transition realized the min.

If stuck: see solution.py.