Algorithm L: Levenshtein Edit Distance

Vladimir Levenshtein, 1965 ("Binary codes capable of correcting deletions, insertions, and reversals")

Strings

Given two strings $A$ and $B$, find the edit distance between them: the minimum number of single-character inserts, deletes, and substitutes needed to transform $A$ into $B$.

Worked example. $A = \texttt{kitten}$, $B = \texttt{sitting}$:

$\texttt{kitten} \to \texttt{sitten}$ (substitute $\texttt{k} \to \texttt{s}$)
$\texttt{sitten} \to \texttt{sittin}$ (substitute $\texttt{e} \to \texttt{i}$)
$\texttt{sittin} \to \texttt{sitting}$ (insert $\texttt{g}$)

So $d(\texttt{kitten}, \texttt{sitting}) = 3$.

The algorithm produces this number without enumerating edit scripts. It builds a matrix where $dp[i][j]$ is the edit distance between $A$'s first $i$ characters and $B$'s first $j$ characters, then reads off $dp[|A|][|B|]$ as the answer.

Why character-level, not byte-level. UTF-8 encodes many scripts with multi-byte characters. A naive byte-level edit distance over those would over-count by the byte-per-character factor and produce nonsense.

For example, in Korean text: UTF-8 represents one Hangul syllable as three bytes. Comparing 안녕 (two syllables, six bytes) to 안녕하세요 (five syllables, fifteen bytes) at the byte level would report nine. The correct character-level answer is three.

The implementation backing the playground below operates on Rust's chars() iterator, which yields one Unicode codepoint per element, so multi-byte text scores correctly regardless of script.

The two-row optimization. A literal $|A| + 1$ by $|B| + 1$ matrix uses $\Theta(|A| \cdot |B|)$ memory.

For two long strings this is wasteful: each cell only depends on the previous row plus the cell to its left. Keeping just two rows ($\textit{prev}$ and $\textit{curr}$) reduces space to $\Theta(\min(|A|, |B|))$ at no cost in time.

The trace below shows both rows at every labeled state.

Computation Method

Initialize prev row

Set $\textit{prev}[j] \leftarrow j$ for $j = 0, 1, \ldots, |B|$. The cost of turning empty $A$ into the first $j$ characters of $B$ is exactly $j$ inserts.

$\textit{prev}[j] \leftarrow j,\ 0 \leq j \leq |B|$

Start new outer row

For each $i$ from $1$ to $|A|$, set $\textit{curr}[0] \leftarrow i$. The cost of turning the first $i$ characters of $A$ into empty $B$ is $i$ deletes.

$\textit{curr}[0] \leftarrow i$

Fill one cell

For each $j$ from $1$ to $|B|$, let $c \leftarrow [A_{i-1} \neq B_{j-1}]$ (the substitute cost: $0$ if the characters match, $1$ otherwise). Then $\textit{curr}[j] \leftarrow \min(\textit{prev}[j] + 1,\ \textit{curr}[j-1] + 1,\ \textit{prev}[j-1] + c)$. The three options correspond to the three edit types: delete, insert, substitute.

$\textit{curr}[j] \leftarrow \min\big(\textit{prev}[j] + 1,\ \textit{curr}[j-1] + 1,\ \textit{prev}[j-1] + c\big)$

Swap rows

After the inner loop completes, the row we just filled becomes the new $\textit{prev}$; the old $\textit{prev}$ buffer is reused as the next $\textit{curr}$. This is the two-row optimization: $\Theta(|B|)$ memory instead of $\Theta(|A| \cdot |B|)$.

$\textit{prev} \leftrightarrow \textit{curr}$

Done

After the outer loop terminates, $\textit{prev}[|B|]$ holds the edit distance between $A$ and $B$ — the minimum number of single-character inserts, deletes, and substitutes that transform $A$ into $B$.

return $\textit{prev}[|B|]$

Why It Works

Key Identity

$$d(A, B) = \min \begin{cases} d(A_{1..i-1}, B_{1..j}) + 1 & \text{(delete)} \\ d(A_{1..i}, B_{1..j-1}) + 1 & \text{(insert)} \\ d(A_{1..i-1}, B_{1..j-1}) + [A_i \neq B_j] & \text{(substitute)} \end{cases}$$

The recurrence asks: 'what was the LAST edit?' Any optimal edit script ends with exactly one of three operations: deleting the last character of $A$, inserting the last character of $B$, or substituting the last character of $A$ for the last character of $B$ (which is free if they already match). Each option reduces the problem to a smaller subproblem whose answer is already computed. The two-row optimization stores only $\textit{prev}$ (row $i-1$) and $\textit{curr}$ (row $i$) because $\textit{dp}[i][j]$ depends on three neighbors: $\textit{dp}[i-1][j]$, $\textit{dp}[i][j-1]$, and $\textit{dp}[i-1][j-1]$ — all in the previous row or one cell to the left in the current row.

Interactive Trace

Step through the dp matrix on real inputs. The active cell is outlined; the three contributors (delete, insert, substitute) are tinted to match the legend.

Complexity: $\Theta(|A| \cdot |B|)$ / Space: $\Theta(\min(|A|, |B|))$ — Each of the $|A| \cdot |B|$ inner cells is visited once and computed in $O(1)$. The two-row dp keeps memory linear in the shorter string (swap $A$ and $B$ if $|A| > |B|$). Faster algorithms exist when distance $\leq k$ is bounded ($O(k \cdot \min(|A|, |B|))$ via the Ukkonen banded approach), but for unrestricted distance the quadratic bound is essentially tight under fine-grained complexity assumptions (SETH).

Review Cards

Conceptual Step

What does step L5 do in Levenshtein Edit Distance, and why does it guarantee progress toward termination?

Invariant

What mathematical identity ensures correctness at each step of Algorithm L?

When to Use

When would you reach for Levenshtein Edit Distance over alternative approaches?

Complexity

What is the time complexity of Levenshtein Edit Distance?