Edit Distance (Levenshtein Distance)

Worked Solution

How to Think About It: The naive move -- search over every sequence of edits -- is a trap: it branches exponentially. The heuristic that cracks it is optimal substructure via last-character alignment. Compare only the *last* characters of the two prefixes $s_1[0..i-1]$ and $s_2[0..j-1]$. Exactly one of four things is optimal for that final position: the two last characters already match (align them for free), or you paid for a delete, an insert, or a substitute. Each choice hands you back a *strictly smaller* prefix pair. That single recurrence is the whole problem; everything else is bookkeeping in an $(m{+}1)\times(n{+}1)$ table. This is the canonical DP / first-step-decomposition pattern -- decide the last operation, recurse on what remains.

Quick Estimate: Before writing code, bound the answer in your head. The edit distance is squeezed between $\big|\,|s_1|-|s_2|\,\big|$ (you must at least insert/delete the length difference) and $\max(|s_1|,|s_2|)$ (worst case: rewrite everything). For kitten (6) $\to$ sitting (7): lower bound $|6-7|=1$, upper bound $7$. The true answer $3$ sits comfortably inside. A sharper mental count: line the words up, sitt is shared in the middle, so you expect only a *handful* of edits -- 'k'$\to$'s', 'e'$\to$'i', and one trailing insert = $3$. For horse$\to$ros: length drop $5-3=2$ forces at least 2 deletes, and one letter differs, so $\approx 3$ -- exactly right. The bound-plus-eyeball is the sanity check an interviewer wants before you commit to the $O(mn)$ table.

Approach: Fill $dp[i][j]$ = edit distance of the first $i$ chars of $s_1$ and first $j$ chars of $s_2$, row by row, using the last-character recurrence.

Formal Solution:

Define $dp[i][j]$ = edit distance between $s_1[0..i-1]$ and $s_2[0..j-1]$.

*Base cases* (one string empty): - $dp[i][0] = i$ -- delete all $i$ characters of $s_1$. - $dp[0][j] = j$ -- insert all $j$ characters of $s_2$.

*Recurrence*, for $i,j \ge 1$: $$dp[i][j] = \begin{cases} dp[i-1][j-1] & \text{if } s_1[i-1] = s_2[j-1] \\[4pt] 1 + \min\!\big(dp[i-1][j],\; dp[i][j-1],\; dp[i-1][j-1]\big) & \text{otherwise} \end{cases}$$ where the three inner terms are delete from $s_1$, insert into $s_1$, and substitute respectively. The answer is $\boxed{dp[m][n]}$ with $m=|s_1|,\, n=|s_2|$.

```python def edit_distance(s1: str, s2: str) -> int: m, n = len(s1), len(s2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if s1[i - 1] == s2[j - 1]: dp[i][j] = dp[i - 1][j - 1] else: dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) return dp[m][n] ```

Space optimization: each row depends only on the row above, so keep two rows and reduce space to $O(\min(m,n))$:

```python def edit_distance_optimized(s1: str, s2: str) -> int: if len(s1) < len(s2): s1, s2 = s2, s1 m, n = len(s1), len(s2) prev = list(range(n + 1)) for i in range(1, m + 1): curr = [i] + [0] * n for j in range(1, n + 1): if s1[i - 1] == s2[j - 1]: curr[j] = prev[j - 1] else: curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1]) prev = curr return prev[n] ```

Complexity: Time $O(mn)$ (each of the $mn$ cells is $O(1)$); space $O(mn)$ for the full table, $O(\min(m,n))$ with two rows.

Answer: Edit distance is computed in $O(mn)$ time by DP; the key insight is that aligning the last characters of each prefix reduces the problem to three strictly smaller subproblems. On the examples: kitten$\to$sitting $=3$, horse$\to$ros $=3$, ""$\to$abc $=3$.