Abstract

Given two words (strings), how can we define a notion of “closeness”?

Definition We can keep track of how many "changes" we need to change one word into another. The changes can be:

insertion

deletion

substitution

For example, lining up the words PELICAN and OSTRICH:

this alignment uses 7 changes, but it is not the cheapest.

Category: Dynamic Programming / String Processing

Input: Two strings $x [1 \dots n]$ and $y [1 \dots m]$

Output: The minimum number of edits (insert/delete/substitute) to transform $x$ into $y$

Paradigm: Dynamic Programming — equivalently, shortest path in a DAG (see below)

Typical use cases: spell checking/correction, diff tools, DNA sequence alignment, fuzzy string matching

Problem Specification

Instance: Two strings $x [1 \dots n]$ , $y [1 \dots m]$ (WLOG $n \leq m$ ).
Solution Format: A sequence of edit operations (insert, delete, substitute) that transforms $x$ into $y$ .
Constraints: The sequence must actually transform $x$ into $y$ exactly.
Objective: The number of edit operations used.
Goal: Minimize.

Candidate Strategies / Approaches

Brute Force ✘

Try all possible alignments/combinations and find the minimum cost among them. A lower bound on how many combinations exist: each of (at least) the first $n$ columns of an alignment table could independently be one of three things (delete, insert, or substitute/match) — so there are at least $3^{n}$ different combinations. Exponential.

Dynamic Programming ✔

Define $E [i, j]$ = the edit distance to transform $x_{1} \dots x_{i}$ into $y_{1} \dots y_{j}$ . Solve smallest prefixes first, reusing each answer.

Dynamic Programming Solution

1. Define Subproblems

Let $E [i, j]$ be the edit distance to transform $x_{1} \dots x_{i}$ into $y_{1} \dots y_{j}$ (the minimum number of changes).

2. Base Cases

When the first word is empty, the edit distance is the length of the second word; when the second word is empty, it’s the length of the first word:

$E [0, j] = j E [i, 0] = i$

3. Express Recursively

What does the last column of the alignment table look like? Three cases:

Case 1 — Delete $x_{i}$ :

$x_{1} \dots x_{i - 1}$	$x_{i}$
$y_{1} \dots y_{j}$	―

$E [i, j] = 1 + E [i - 1, j]$

Case 2 — Insert $y_{j}$ :

$x_{1} \dots x_{i}$	―
$y_{1} \dots y_{j - 1}$	$y_{j}$

$E [i, j] = 1 + E [i, j - 1]$

Case 3 — Substitute (or match, if equal):

$x_{1} \dots x_{i - 1}$	$x_{i}$
$y_{1} \dots y_{j - 1}$	$y_{j}$

$E [i, j] = {1 + E [i - 1, j - 1] if x_{i} \neq = y_{j} 0 + E [i - 1, j - 1] if x_{i} = y_{j}$

Since we don’t know which case is cheapest, take the minimum of all three.

4. Ordering

To calculate $E [i, j]$ , we need $E [i - 1, j]$ , $E [i, j - 1]$ , and $E [i - 1, j - 1]$ — all already computed if we visit cells left to right through rows, top to bottom.

5. Iterative Algorithm

Algorithm 17 Edit Distance

procedure EditDist( $x[1\dots n], y[1 \dots m]$ )

for $i$ from $1$ to $n$ do

$E[i, 0] = i$

for $j$ from $1$ to $m$ do

$E[0, j] = j$

for $i$ from $1$ to $n$ do

for $j$ from $1$ to $m$ do

if $x[i] == y[j]$ then

$E[i, j] = \min(1 + E[i-1, j], 1 + E[i, j-1], 0 + E[i-1, j-1])$

if $x[i] \neq y[j]$ then

$E[i, j] = \min(1 + E[i-1, j], 1 + E[i, j-1], 1 + E[i-1, j-1])$

return $E[n, m]$

6. Final Output

$E [n, m]$

Variables & Data Structures

Name	Type	Purpose
`E`	2D array, $(n + 1) \times (m + 1)$	`E[i][j]` = edit distance between $x_{1} \dots x_{i}$ and $y_{1} \dots y_{j}$

Helper Functions / Operations Used

Character comparison x[i] == y[j] — $O (1)$ .

Edit Distance as a DAG

This table can be viewed as a DAG:

This graph has $∣ V ∣ = nm$ vertices and $∣ E ∣ \approx 3 nm$ edges (each cell has up to 3 incoming edges — from the delete, insert, and substitute/match cases above). The goal becomes: find the length of the shortest path from the top-left corner $(0, 0)$ to the bottom-right corner $(n, m)$ .

We could use Dijkstra’s Algorithm for a runtime of:

$O (nm lo g (nm))$

But there’s a faster way, using the fact that this graph is specifically a DAG — see Shortest Path in a DAG Example.

Why This Connection Matters

The DP recurrence above is a shortest-path-in-a-DAG algorithm, just described in array terms instead of graph terms: filling E row by row, left to right is exactly a topological order of this DAG, and each cell’s min over three incoming edges is exactly the DAG shortest-path relaxation step. That’s why the DP solution’s own $O (nm)$ runtime already beats Dijkstra’s $O (nm lo g (nm))$ — it’s implicitly using the DAG structure (no comparisons/priority queue needed) rather than Dijkstra’s general-graph machinery.

Proof of Correctness / Optimality

Claim: $E [i, j]$ equals the true minimum edit distance between $x_{1} \dots x_{i}$ and $y_{1} \dots y_{j}$ .

Base cases: $E [0, j] = j$ (transform empty string to $y_{1} \dots y_{j}$ by $j$ insertions) and $E [i, 0] = i$ (transform $x_{1} \dots x_{i}$ to empty by $i$ deletions) are both correct by inspection — there’s no cheaper way to create or destroy $k$ characters than $k$ single-character operations.
Inductive Hypothesis: every cell visited before $(i, j)$ in the row-by-row, top-to-bottom order — in particular $E [i - 1, j]$ , $E [i, j - 1]$ , $E [i - 1, j - 1]$ — is correct.
Inductive Step: the last operation in any optimal transformation of $x_{1} \dots x_{i}$ into $y_{1} \dots y_{j}$ must be one of exactly three things: delete $x_{i}$ , insert $y_{j}$ , or substitute/match $x_{i}$ with $y_{j}$ . Each case’s cost is $1$ (or $0$ for a free match) plus the cost of optimally solving the remaining smaller prefix problem — which is correct by the Inductive Hypothesis. Since $E [i, j]$ takes the minimum over exactly these three cases, and every valid transformation’s last step falls into one of them, $E [i, j]$ is the true minimum.

Time & Space Complexity Analysis

General Case

	Complexity	Notes
Time	$O (nm)$	One $O (1)$ computation per cell, $(n + 1) \times (m + 1)$ cells
Space	$O (nm)$	The full table; reducible to $O (min (n, m))$ if only the distance value is needed (keep just the current and previous row), at the cost of losing the ability to reconstruct the actual edit sequence

Best / Worst / Average Case

Best / Worst / Average case: all $O (nm)$ — every cell is filled regardless of how similar or different the two strings are.

Drawbacks / Constraints

Doesn’t directly output the edit sequence, only its length — recovering the actual operations (like String Reconstruction’s prev pointers) requires tracing back through the table from $(n, m)$ to $(0, 0)$ , following whichever case achieved the minimum at each step.
$O (nm)$ space can be heavy for very long strings if the full table is kept; see the space-reduction note above when only the distance value is needed.
All operations cost the same (1 each) here. A weighted variant (e.g. substitutions costing more than insertions, or cost depending on which characters are involved) is a natural extension — same recurrence shape, different constants per case.

Jason's Notebook

Explorer

Edit Distance Example