Levenshtein Edit Distance

Background

Levenshtein distance is the minimum number of single-character insertions, deletions, and substitutions to turn one string into another. Foundational primitive for spell-check, fuzzy matching, DNA alignment, and the classic dynamic-programming exercise. $O(|a| \cdot |b|)$ time and space.

Problem statement

Implement levenshtein(a, b) via the canonical 2-D DP:

$$\text{dp}[i][j] = \begin{cases} i & j = 0 \\ j & i = 0 \\ \text{dp}[i-1][j-1] & a_{i-1} = b_{j-1} \\ 1 + \min(\text{dp}[i-1][j],\ \text{dp}[i][j-1],\ \text{dp}[i-1][j-1]) & \text{otherwise} \end{cases}$$

Return dp[len(a)][len(b)].

Input

• a — str.
• b — str.

Output

Returns int >= 0, the edit distance.

Examples

Example 1 — classic worked example

Input:  a="kitten", b="sitting"
Output: 3

Explanation: kitten → sitten (sub k→s) → sittin (sub e→i) → sitting (insert g). Three edits.

Example 2 — identical strings

Input:  a="abc", b="abc"
Output: 0

Example 3 — empty cases

Input:  a="", b="abc" → 3
Input:  a="abc", b="" → 3
Input:  a="", b="" → 0

Example 4 — single substitution

Input:  a="cat", b="bat"
Output: 1

Example 5 — insertion at the end

Input:  a="abc", b="abcd"
Output: 1

Constraints

• Allowed edits: insert, delete, substitute (all cost 1).
• Empty inputs return the length of the other string.
• $O(|a| \cdot |b|)$ time and space is acceptable.

Notes

• Space optimisation. You only need the previous row of the DP table; that drops memory to $O(\min(|a|, |b|))$.
• Variants. Damerau-Levenshtein adds a transposition operation; Hamming forbids insertion/deletion (only substitutions). Same DP shape, different recurrence.