13.10 Edit Distance
The edit distance problem asks a deceptively simple question: > How different are two strings?
13.10 Edit Distance
The edit distance problem asks a deceptively simple question:
How different are two strings?
At first glance, comparing strings appears straightforward. We can count mismatched characters or compare lengths. Unfortunately, such approaches fail as soon as insertions and deletions are introduced. A single inserted character shifts every subsequent position, making naive comparisons meaningless.
Edit distance solves this problem by measuring the minimum number of operations required to transform one string into another. The resulting algorithm forms the foundation of spell checkers, search engines, DNA sequence alignment tools, plagiarism detectors, data synchronization systems, and fuzzy matching libraries.
From a dynamic programming perspective, edit distance is particularly important because it demonstrates how a recurrence can emerge directly from the legal operations of a problem. Every transition in the dynamic programming table corresponds to a concrete edit operation, making the connection between problem statement and recurrence unusually clear.
Problem
Given two strings:
kitten
sitting
Transform the first string into the second using:
- insertion
- deletion
- replacement
Each operation costs one unit.
Find the minimum total cost.
One valid transformation is:
kitten
↓
sitten
↓
sittin
↓
sitting
Total cost:
3
The edit distance equals three.
Why Simple Comparisons Fail
Consider:
ABCDEF
ABXDEF
Only one replacement is required.
Distance:
1
Now consider:
ABCDEF
ABXCDEF
A single insertion transforms one string into the other.
Distance:
1
A character-by-character comparison would report many differences because every character after:
X
appears shifted.
The challenge is determining the best alignment between the two strings.
Designing the State
As with Longest Common Subsequence, the natural subproblem involves prefixes.
Define:
$$ dp[i][j] $$
as:
The minimum edit distance between the first (i) characters of string A and the first (j) characters of string B.
For example:
$$ dp[4][3] $$
asks:
What is the minimum cost
to transform
A[0...3]
into
B[0...2]?
This definition immediately produces smaller subproblems of the same form.
Understanding the Final Operation
Suppose we want to compute:
$$ dp[i][j] $$
Focus on the final characters:
A[i-1]
B[j-1]
Every valid transformation must end with one of several possibilities.
Characters Already Match
Suppose:
A[i-1] == B[j-1]
No edit is necessary.
The problem reduces directly to:
$$ dp[i-1][j-1] $$
Therefore:
$$ dp[i][j] = dp[i-1][j-1] $$
This is the cheapest possible situation.
Replacement
Suppose the final characters differ.
We may replace:
A[i-1]
with:
B[j-1]
Cost:
$$ 1 + dp[i-1][j-1] $$
The replacement fixes both final characters simultaneously.
Deletion
Delete:
A[i-1]
The final character of A disappears.
Cost:
$$ 1 + dp[i-1][j] $$
The remaining prefixes must still be transformed.
Insertion
Insert:
B[j-1]
into A.
Cost:
$$ 1 + dp[i][j-1] $$
The insertion accounts for the final character of B.
Complete Recurrence
When characters match:
$$ dp[i][j] = dp[i-1][j-1] $$
Otherwise:
$$ dp[i][j] = 1 + \min ( dp[i-1][j], dp[i][j-1], dp[i-1][j-1] ) $$
This recurrence directly mirrors the three available edit operations.
One of the most satisfying aspects of edit distance is that every term has a clear interpretation.
Base Cases
Suppose one string is empty.
Transforming:
""
into:
ABC
requires:
3 insertions
Therefore:
$$ dp[0][j] = j $$
Similarly:
$$ dp[i][0] = i $$
because:
i deletions
are required.
The first row and first column can be filled immediately.
Building the Table
Consider:
A = CAT
B = CUT
The table begins:
| Ø | C | U | T | |
|---|---|---|---|---|
| Ø | 0 | 1 | 2 | 3 |
| C | 1 | 0 | 1 | 2 |
| A | 2 | 1 | 1 | 2 |
| T | 3 | 2 | 2 | 1 |
The final answer appears in:
$$ dp[3][3] $$
which equals:
$$ 1 $$
Only a single replacement is required.
Implementation
func EditDistance(a, b string) int {
n := len(a)
m := len(b)
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, m+1)
}
for i := 0; i <= n; i++ {
dp[i][0] = i
}
for j := 0; j <= m; j++ {
dp[0][j] = j
}
for i := 1; i <= n; i++ {
for j := 1; j <= m; j++ {
if a[i-1] == b[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[n][m]
}
The code follows the recurrence almost verbatim.
Visualizing Dependencies
Each cell depends on three neighboring cells.
↖ ↑
← current
Interpretation:
↖ replacement
↑ deletion
← insertion
Unlike LCS, every dependency corresponds directly to a concrete operation.
This relationship makes edit distance particularly intuitive.
Recovering the Edit Script
The distance alone is often insufficient.
Many applications require the actual sequence of edits.
Starting from:
$$ dp[n][m] $$
walk backward.
If characters match:
move diagonally
If:
$$ dp[i][j] = dp[i-1][j-1]+1 $$
record:
replace
If:
$$ dp[i][j] = dp[i-1][j]+1 $$
record:
delete
If:
$$ dp[i][j] = dp[i][j-1]+1 $$
record:
insert
The resulting path describes an optimal transformation.
Many diff tools operate in a similar manner.
Space Optimization
Observe that row:
$$ i $$
depends only on:
- row (i-1)
- current row
Store two rows:
previous := make([]int, m+1)
current := make([]int, m+1)
Memory decreases from:
$$ O(nm) $$
to:
$$ O(m) $$
This optimization is useful when processing large documents.
Weighted Edit Distance
Not all edits must have equal cost.
For example:
insert = 1
delete = 1
replace = 2
The recurrence becomes:
$$ dp[i][j] = \min ( dp[i-1][j]+deleteCost, dp[i][j-1]+insertCost, dp[i-1][j-1]+replaceCost ) $$
Only the transition costs change.
The dynamic programming structure remains identical.
Relationship to Longest Common Subsequence
LCS and edit distance are closely related.
Suppose only insertions and deletions are allowed.
Then:
$$ EditDistance = |A| + |B| - 2 \times LCS $$
Both algorithms compare prefixes.
Both use a two-dimensional table.
Both depend on diagonal, left, and upward transitions.
Learning one makes the other easier to understand.
Applications
Edit distance appears throughout software systems.
Spell Checking
Search for dictionary words with minimal edit distance from the query.
Example:
recieve
becomes:
receive
Search Engines
Support fuzzy matching for misspelled queries.
DNA Analysis
Measure similarity between genetic sequences.
Data Synchronization
Identify changes between document versions.
OCR Systems
Correct recognition errors by comparing words against known dictionaries.
Entity Matching
Detect similar names:
Jon Smith
John Smith
despite small differences.
Common Mistakes
Incorrect Initialization
The first row and first column must represent transformations involving empty strings.
Most implementation errors begin here.
Forgetting the Match Case
When characters are equal:
$$ dp[i][j] = dp[i-1][j-1] $$
Adding an unnecessary cost produces incorrect results.
Confusing Operations
The recurrence terms correspond to:
up = deletion
left = insertion
diagonal = replacement
Mixing these interpretations causes reconstruction errors.
Off-by-One Errors
The table dimensions are:
$$ (n+1)\times(m+1) $$
while character indices begin at zero.
Careful indexing is essential.
Complexity Analysis
State count:
$$ (n+1)(m+1) $$
Each state performs constant work.
Time complexity:
$$ O(nm) $$
Memory complexity:
$$ O(nm) $$
or:
$$ O(m) $$
with row compression.
Takeaway
Edit distance demonstrates one of the most elegant applications of dynamic programming. The state space models transformations between string prefixes, while the recurrence directly encodes the legal edit operations. The resulting algorithm computes optimal transformations in (O(nm)) time and forms the foundation of numerous systems involving approximate matching, synchronization, search, and sequence analysis. More broadly, edit distance illustrates a recurring dynamic programming pattern: when a problem can be expressed as a sequence of local transformations, the optimal global solution often emerges naturally from a carefully designed recurrence.