DPAlgorithmaka Levenshtein distance, string alignment

Edit Distance

Minimum number of insertions, deletions, and substitutions to turn one string into another via a 2D prefix table.

▶ Visualize Pattern: Dynamic Programming Practice (2)

Progress

Overview

The edit (Levenshtein) distance between a and b is the fewest single-character operations — insert, delete, replace — that transform a into b. "horse" → "ros" takes 3: replace h→r, delete r, delete e. It powers spell-checkers, fuzzy search, and sequence alignment.

The table is the same shape as Longest Common Subsequence: dp[i][j] is the distance between prefixes a[:i] and b[:j]. The difference is three incoming moves instead of two, all with cost 1 (or 0 for a match on the diagonal).

2D DPtwo stringsLevenshteinO(n·m)rolling rows

Intuition

A mental model before the formal terms.

Transform "cat" into "cut". Look at the last characters: t == t, so nothing to do there; the problem reduces to "ca" → "cu". Now a != u: either replace a with u (cost 1, then "c" → "c"), delete a (cost 1, then "c" → "cu"), or insert u at the end (cost 1, then "ca" → "c"). The cheapest is replace: total 1.

On the grid, moving down deletes a character of a, moving right inserts a character of b, and moving diagonally either matches (free) or substitutes (cost 1). The edit distance is the cheapest path from the top-left corner to the bottom-right corner, where the first row and column are the trivial "insert everything" / "delete everything" paths.

How it works

State: dp[i][j] = minimum edits to convert a[0..i) into b[0..j).
Transition: if a[i-1] == b[j-1], dp[i][j] = dp[i-1][j-1]; otherwise dp[i][j] = 1 + min(dp[i-1][j-1] (replace), dp[i-1][j] (delete a[i-1]), dp[i][j-1] (insert b[j-1])).
Base case: dp[i][0] = i (delete all of a[:i]), dp[0][j] = j (insert all of b[:j]).
Iteration order: row-major, i from 1 to n, j from 1 to m.
Answer location: dp[n][m].
Space optimization: two rows (or one row plus a saved diagonal value) suffice, since each cell reads only the current and previous row. Put the shorter string on the columns for O(min(n, m)).

Why it works

Optimal substructure: consider an optimal edit script for a[:i] → b[:j] and look at how the last character of the result b[j-1] was produced. Either it was inserted (the rest is an optimal script for a[:i] → b[:j-1]), or a[i-1] was deleted (rest: a[:i-1] → b[:j]), or a[i-1] was matched/replaced to b[j-1] (rest: a[:i-1] → b[:j-1]). In each case the remainder must be optimal for its subproblem, else the whole script could be shortened. The transition minimizes over exactly these three cases.

Operations can be reordered so that edits are applied left to right without changing the cost, which is what lets us reason about "the last character" cleanly.

There are (n+1)(m+1) states with O(1) work each; the table is an explicit shortest path on a DAG, and row-major order is a topological order of that DAG.

Recognition

How to tell a problem wants this.

"Minimum operations to convert string A to string B" with a small fixed set of operations.
Fuzzy matching, spell correction, "are these strings within k edits".
Variants: only insert/delete (n + m - 2·LCS), weighted operations, or allowing adjacent transposition (Damerau).

“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

Word A | word B — Two words separated by a pipe — e.g. "kitten | sitting". Up to 10 characters each

		s	i	t	t	i	n	g
	0	1	2	3	4	5	6	7
k	1	·	·	·	·	·	·	·
i	2	·	·	·	·	·	·	·
t	3	·	·	·	·	·	·	·
t	4	·	·	·	·	·	·	·
e	5	·	·	·	·	·	·	·
n	6	·	·	·	·	·	·	·

1/44Turning a prefix into the empty string costs one deletion per character (column 0); building it from empty costs one insertion per character (row 0).

Cell being filledDependency readBase caseComputedReconstructed choice

PseudocodeLearn Edit Distance →

1dp[i][0] = i; dp[0][j] = j
2for i in 1 .. m: for j in 1 .. n:
3  if A[i] == B[j]: dp[i][j] = dp[i-1][j-1]
4  else: dp[i][j] = 1 + min(dp[i-1][j-1] replace, dp[i-1][j] delete, dp[i][j-1] insert)
5traceback from dp[m][n]

Variables

Complexity

best O(n·m)

avg O(n·m)

worst O(n·m)

space O(min(n, m))

Speed

Pseudocode

1dp[i][0] = i, dp[0][j] = j
2for i in 1..n:
3  for j in 1..m:
4    if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1]
5    else: dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
6return dp[n][m]

Implementations

1# dp[i][j] = minimum edits (insert/delete/replace) turning a[0..i) into b[0..j)
2def edit_distance(a: str, b: str) -> int:
3    n, m = len(a), len(b)
41 · State table
5    dp = [[0] * (m + 1) for _ in range(n + 1)]
62 · Base cases
7    for i in range(n + 1):
8        dp[i][0] = i  # delete all of a[0..i)
9    for j in range(m + 1):
10        dp[0][j] = j  # insert all of b[0..j)
113 · Transition
12    for i in range(1, n + 1):
13        for j in range(1, m + 1):
14            if a[i - 1] == b[j - 1]:
15                dp[i][j] = dp[i - 1][j - 1]  # characters agree: free
16            else:
17                dp[i][j] = 1 + min(
18                    dp[i - 1][j - 1],  # replace a[i-1] with b[j-1]
19                    dp[i - 1][j],      # delete a[i-1]
20                    dp[i][j - 1],      # insert b[j-1]
21                )
224 · Answer
23    return dp[n][m]

Walkthrough

Fresh rows come from the list comprehension; the two base-case loops then write the frame (dp[i][0] = i, dp[0][j] = j).
min with three arguments picks the cheapest predecessor; adding 1 converts it into "one more edit".
The match branch is a pure diagonal copy — matching characters cost nothing.
dp[n][m] is the Levenshtein distance between the full strings.

Complexity (this implementation)

time O(n·m) · space O(n·m)

Two rows → O(min(n, m)). Pure-Python nested loops are slow for n·m in the tens of millions; the same table in C (python-Levenshtein) or numpy is orders of magnitude faster.

Language notes

Python strings index by code point, so emoji and accents behave correctly — unlike JS/TS UTF-16 code units.
min(a, b, c) with positional args beats min([a, b, c]) — no list allocation per cell.
functools.lru_cache on a recursive formulation is elegant but recursion depth is n + m; the iterative table avoids the limit.

Common mistakes in this language

The [[0] * m] * n aliasing bug when building the table.
Writing the base cases only for dp[0][0].
Adding 1 to the diagonal on matches — that answers a different question (every position costs).

Language differences that matter here

Character semantics differ: Python indexes by code point, JS/TS by UTF-16 code unit (emoji count as two), C++ std::string by byte — identical algorithms can disagree on non-ASCII input.
Three-way min: C++ needs std::min({a, b, c}) (initializer list), JS/TS Math.min(a, b, c), Python min(a, b, c) — all constant-time for three args.
Row aliasing when building the 2D table bites Python (* on a list of lists) and JS/TS (fill with one object); C++ value semantics make each row independent.

Complexity

Best

O(n·m)

Average

O(n·m)

Worst

O(n·m)

Space

O(min(n, m))

If only "distance ≤ k?" is needed, banded DP restricted to |i − j| ≤ k runs in O(k · min(n, m)).

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when

Minimum-cost transformation between two strings with per-character operations.
Approximate string matching and spelling correction, possibly with weighted operation costs.
Any two-sequence alignment (bioinformatics Needleman–Wunsch is edit distance with a scoring matrix).

Avoid it when

Only insert/delete are allowed — compute via Longest Common Subsequence, which is simpler and gives the alignment directly.
Very long strings with a small distance bound — use the banded or diagonal (Ukkonen / Myers) algorithms instead of the full table.
Comparing many strings against a dictionary — a Trie with edit-distance pruning or a BK-tree beats repeated full tables.

Alternatives

Longest Common Subsequence Trie Subsequence DP

Common mistakes

Forgetting the base rows dp[i][0] = i and dp[0][j] = j (leaving them 0 makes the distance zero for any pair).
Adding 1 on the diagonal even when the characters match.
Swapping the meaning of "insert" and "delete" in the rolling version and then mis-initializing cur[0].
Using the one-row version without saving the diagonal prev[j-1] before overwriting it.

Interview patterns

Edit Distance (Levenshtein) between two words.
One Edit Distance: check in O(n) without a table.
Minimum ASCII Delete Sum / Delete Operation for Two Strings — weighted or restricted variants.
Regular Expression / Wildcard Matching: same table shape with different transitions.

Interview questions on this

Choosing between BFS, DFS, Dijkstra and DPAdvanced
When space complexity mattersIntermediate
Choosing a shortest-path algorithmAdvanced
Recognizing a dynamic-programming problemAdvanced

Mock interviews

Coin ChangeIntermediate

Example problems

Longest Common Subsequencemedium Edit Distancemedium

		s	i	t	t	i	n	g
	0	1	2	3	4	5	6	7
k	1	·	·	·	·	·	·	·
i	2	·	·	·	·	·	·	·
t	3	·	·	·	·	·	·	·
t	4	·	·	·	·	·	·	·
e	5	·	·	·	·	·	·	·
n	6	·	·	·	·	·	·	·

		s	i	t	t	i	n	g
	0	1	2	3	4	5	6	7
k	1	·	·	·	·	·	·	·
i	2	·	·	·	·	·	·	·
t	3	·	·	·	·	·	·	·
t	4	·	·	·	·	·	·	·
e	5	·	·	·	·	·	·	·
n	6	·	·	·	·	·	·	·

Overview

Intuition

How it works

Why it works

Recognition

Interactive visualization

Pseudocode

Implementations

Complexity

When to use — and when not to

Alternatives

Common mistakes

Interview patterns

Example problems

Related

		s	i	t	t	i	n	g
	0	1	2	3	4	5	6	7
k	1	·	·	·	·	·	·	·
i	2	·	·	·	·	·	·	·
t	3	·	·	·	·	·	·	·
t	4	·	·	·	·	·	·	·
e	5	·	·	·	·	·	·	·
n	6	·	·	·	·	·	·	·