Edit Distance
Given two words, return the minimum number of single-character insertions, deletions or substitutions required to transform the first into the second.
- 0 ≤ word1.length, word2.length ≤ 500
- Lowercase English letters
- Minimum edits between two sequences
- Prefix pairs define the state — 2D table
- Three transitions per cell: insert, delete, replace
Counting or optimizing over choices where a brute-force recursion revisits the same state signals DP: define the state so the answer to a state depends only on smaller states, then memoize or fill a table bottom-up. Subsequence (not subarray) wording, "number of ways", and "minimum/maximum over all choices" are the classic tells.
Let D[i][j] be the distance between the first i characters of word1 and the first j of word2; the borders are D[i][0] = i and D[0][j] = j. If the current characters match, D[i][j] = D[i-1][j-1]; otherwise it is one plus the minimum of D[i-1][j] (delete), D[i][j-1] (insert) and D[i-1][j-1] (replace). Fill the table in order and read D[m][n].
- Ukkonen's banded variant runs in O(k · min(m, n)) when the answer is known to be ≤ k. Memoized recursion is equivalent but slower in practice.