vault

Edit Distance

17 min read

Edit Distance

The Edit Distance (also called Levenshtein distance) between two strings A and B is the minimum number of single-character edit operations — insert, delete, or substitute — required to transform A into B. For A = "kitten" and B = "sitting", the edit distance is 3 (substitute k→s, substitute e→i, insert g). It is the workhorse algorithm behind spell-checkers (suggest the dictionary word with smallest edit distance from the typo), fuzzy text matching, DNA sequence alignment, plagiarism detection, and approximate database joins. The classical 2D DP solution by Wagner & Fischer (JACM 1974) runs in O(mn) time and O(mn) space, reducible to O(min(m, n)) space; the underlying recurrence is a three-way sibling of Longest Common Subsequence.

1. Intuition — “Type, Backspace, Overwrite”

Imagine you have two windows open in a text editor: one shows the source string A, one shows the target B. You want to make A look like B using the smallest number of keystrokes, where each keystroke is exactly one of:

  • Insert a character (you press a letter key — adds one character somewhere).
  • Delete a character (you press Backspace — removes one character).
  • Substitute a character (you delete one and insert another — but this counts as one operation, not two, in the standard Levenshtein formulation).

The edit distance is the minimum keystroke count. This is exactly what spell-checkers compute: when you type “speling” the checker compares it against every word in the dictionary, computes the edit distance, and offers the closest matches (“spelling” — distance 1) as suggestions.

The historical context: V. I. Levenshtein introduced this distance in 1965 in a paper on coding theory, asking how many bit errors a code could detect and correct. R. A. Wagner and M. J. Fischer in 1974 (JACM) gave the textbook O(mn) DP we still use today, generalizing Levenshtein’s recursive definition into the now-canonical bottom-up table fill. Their paper is titled “The String-to-String Correction Problem” and is also the reference for Longest Common Subsequence — the two problems share the same machinery and the same year of publication.

The recognition signal in interview problems: anywhere you see “minimum operations to transform / convert / match / align two strings with insert/delete/substitute,” it’s edit distance. Variants substitute different operation sets — the Damerau-Levenshtein distance adds transposition of adjacent characters (one extra recurrence branch), the Longest Common Subsequence distance bans substitution entirely (only insert and delete; reduces to m + n − 2·LCS).

2. Tiny Worked Example

Let A = "horse" (length m = 5) and B = "ros" (length n = 3). What is the edit distance?

State: dp[i][j] = edit distance between the first i characters of A and the first j characters of B.

Recurrence:

dp[i][j] = dp[i-1][j-1]                                  if A[i-1] == B[j-1]
        = 1 + min( dp[i-1][j],      # delete A[i-1]
                   dp[i][j-1],      # insert B[j-1]
                   dp[i-1][j-1] )   # substitute A[i-1] → B[j-1]
                                                          otherwise

Symbol-by-symbol unpacking:

  • A[i-1], B[j-1] — the last characters of the prefixes (1-indexed prefix length, 0-indexed string access).
  • If they match, no edit is needed for the last position; the cost is just the edit distance of the shorter prefixes (dp[i-1][j-1]).
  • Otherwise, we pay one operation and reduce to a smaller subproblem:
    • Delete A[i-1]: now we need to match A[..i-1] against B[..j] — cost dp[i-1][j] + 1.
    • Insert B[j-1]: now we need to match A[..i] against B[..j-1] (because we’ve already “produced” B[j-1] via the insertion) — cost dp[i][j-1] + 1.
    • Substitute A[i-1] with B[j-1]: both shorten — cost dp[i-1][j-1] + 1.
  • Take the minimum.

Base cases: dp[0][j] = j (turn empty string into B[..j] requires j insertions); dp[i][0] = i (turn A[..i] into empty requires i deletions). These are not zero — a frequent bug.

Build the table with rows = characters of A, columns = characters of B:

After filling base row 0 and column 0:

εros
ε0123
h1
o2
r3
s4
e5

Compute cells one by one. dp[1][1]: A[0]='h' ≠ B[0]='r', so 1 + min(dp[0][1], dp[1][0], dp[0][0]) = 1 + min(1, 1, 0) = 1.

After completing the table:

εros
ε0123
h1123
o2212
r3222
s4332
e5443

Answer: dp[5][3] = 3.

Let’s verify cell dp[2][2] (transform “ho” into “ro”): chars o == o, so dp[2][2] = dp[1][1] = 1. (Edit “h”→“r”, keep “o”.) ✓

Cell dp[5][3] (“horse” → “ros”): chars e ≠ s, so 1 + min(dp[4][3], dp[5][2], dp[4][2]) = 1 + min(2, 3, 3) = 3. The minimizing predecessor is dp[4][3] = 2, which corresponds to deleting the e. So one optimal edit sequence is: “horse” → “horss” (substitute e→s, no — wait, the sequence reconstructs differently). The classic optimal edit sequence for horse→ros is: substitute h→r → “rorse”, delete o → “rrse”, delete… actually the cleaner sequence: delete h → “orse”, substitute o→r → “rrse”… Multiple equally-optimal paths exist; any of length 3 is correct.

3. Pseudocode

edit_distance(A, B):
    m, n := length(A), length(B)
    dp := 2D array of size (m+1) × (n+1)
    for i := 0 to m: dp[i][0] := i
    for j := 0 to n: dp[0][j] := j
    for i := 1 to m:
        for j := 1 to n:
            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],     # delete
                                    dp[i][j-1],     # insert
                                    dp[i-1][j-1])   # substitute
    return dp[m][n]

Note: when A[i-1] == B[j-1] we cannot take the minimum over dp[i-1][j-1] + 1 and the other two — we use the diagonal directly with no cost. This subtlety is the most common implementation mistake (see §11.3).

4. Python Implementation

4.1 Bottom-Up Tabulation, 2D

def edit_distance(A: str, B: str) -> int:
    m, n = len(A), len(B)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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],      # delete from A
                                   dp[i][j - 1],      # insert into A
                                   dp[i - 1][j - 1])  # substitute
    return dp[m][n]

4.2 Bottom-Up, 1D Rolling Array

Each row depends only on the previous row plus the just-computed cell to the left. With careful bookkeeping, one row plus a scalar suffices:

def edit_distance_1d(A: str, B: str) -> int:
    if len(A) < len(B):
        A, B = B, A                                       # ensure inner loop is shorter
    m, n = len(A), len(B)
    prev = list(range(n + 1))                             # base case row dp[0][j] = j
    curr = [0] * (n + 1)
    for i in range(1, m + 1):
        curr[0] = i                                       # base case dp[i][0] = i
        for j in range(1, n + 1):
            if A[i - 1] == B[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
        prev, curr = curr, prev
    return prev[n]

O(min(m, n)) space. Loses the ability to reconstruct the edit sequence.

4.3 Top-Down Memoization

from functools import lru_cache
 
def edit_distance_memo(A: str, B: str) -> int:
    @lru_cache(maxsize=None)
    def helper(i: int, j: int) -> int:
        if i == 0:
            return j
        if j == 0:
            return i
        if A[i - 1] == B[j - 1]:
            return helper(i - 1, j - 1)
        return 1 + min(helper(i - 1, j),
                       helper(i, j - 1),
                       helper(i - 1, j - 1))
    return helper(len(A), len(B))

Mirrors the math directly; clearest for explanation. See Memoization vs Tabulation for trade-off discussion.

5. Complexity

Time: O(mn). There are (m+1)(n+1) cells; each is a min over three predecessors plus a comparison — O(1) per cell.

Space: O(mn) for the 2D table; O(min(m, n)) for the rolling-array version; O(min(m, n)) for Hirschberg-style divide-and-conquer (which also recovers the alignment).

Lower bound: as for Longest Common Subsequence, Backurs & Indyk (2015 STOC) proved that a truly subquadratic edit-distance algorithm would refute the Strong Exponential Time Hypothesis (SETH). So O(mn) is essentially tight in the general case.

Practical speedup for similar strings: Ukkonen’s 1985 algorithm computes edit distance in O((m + n) · D) where D is the actual edit distance — by restricting the DP to a band of width O(D) around the diagonal. Excellent for spell-check (typos differ from real words by D ≤ 2 typically), so the work is O(n) rather than O(n²).

6. Reconstructing the Alignment

The edit distance is a number; the edit script (the actual sequence of inserts/deletes/substitutes) is recovered by backtracking through the table:

def edit_distance_with_script(A: str, B: str) -> tuple[int, list[str]]:
    m, n = len(A), len(B)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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])
    # backtrack
    i, j = m, n
    script = []
    while i > 0 or j > 0:
        if i > 0 and j > 0 and A[i - 1] == B[j - 1]:
            script.append(f"keep {A[i - 1]}")
            i -= 1; j -= 1
        elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1:
            script.append(f"substitute {A[i - 1]} -> {B[j - 1]}")
            i -= 1; j -= 1
        elif i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            script.append(f"delete {A[i - 1]}")
            i -= 1
        else:                                             # j > 0 and inserted
            script.append(f"insert {B[j - 1]}")
            j -= 1
    script.reverse()
    return dp[m][n], script

The order of comparisons in the backtracking branch determines tie-breaking when multiple optimal edit scripts exist.

For an alignment-style display (showing both strings with gaps inserted to mark inserts/deletes), build two parallel character lists during backtracking: when substituting, append both characters; when deleting, append A[i-1] and -; when inserting, append - and B[j-1].

7. Weighted Edit Distance

The Levenshtein recurrence assumes each operation costs 1. Generalize by parameterizing:

  • c_ins(c) — cost of inserting character c.
  • c_del(c) — cost of deleting character c.
  • c_sub(c1, c2) — cost of substituting c1 with c2 (typically 0 if c1 == c2).

Recurrence becomes:

dp[i][j] = min(
    dp[i-1][j] + c_del(A[i-1]),
    dp[i][j-1] + c_ins(B[j-1]),
    dp[i-1][j-1] + c_sub(A[i-1], B[j-1])
)

Applications:

  • Bioinformatics: BLOSUM and PAM substitution matrices in protein alignment assign different mismatch costs based on biochemical similarity (substituting a hydrophobic residue with another hydrophobic residue is cheaper than substituting it with a polar one).
  • Spell-check: typos involving adjacent keys on the QWERTY keyboard (‘a’ vs ‘s’) should cost less than substitutions across the keyboard (‘a’ vs ‘p’).
  • OCR error correction: visual confusables (‘0’ vs ‘O’, ‘1’ vs ‘l’) get cheaper substitution costs.

The DP machinery is identical; only the recurrence weights change. Complexity is unchanged at O(mn).

8. Relationship to LCS

Longest Common Subsequence and edit distance are closely related but not identical:

  • LCS-based distance (insertions and deletions only, no substitution): dist(A, B) = m + n − 2 · LCS(A, B).
  • Levenshtein distance (insert, delete, substitute): always ≤ LCS-based distance, because substitution can be cheaper than delete-then-insert.

Specifically, Levenshtein(A, B) = max(m, n) − LCS(A, B) does not hold in general — it’s a common confusion. The correct statement: each substitution in the Levenshtein script saves one operation compared to the corresponding delete+insert pair in the LCS-based script. So Levenshtein ≤ m + n − 2·LCS = max(m, n) − LCS + min(m, n) − LCS.

The DP recurrence for the LCS-based distance is the same shape but without the substitution branch — only delete and insert (and the diagonal “free move” on a match):

dist[i][j] = min(dist[i-1][j] + 1, dist[i][j-1] + 1)        (mismatch case)
           = dist[i-1][j-1]                                  (match case)

This is almost the same as the Levenshtein recurrence; the substitution branch is the only difference. A useful interview drill: derive both from the same template by toggling allowed operations.

9. Variants Worth Knowing

9.1 Damerau-Levenshtein (with Transposition)

Adds a fourth operation: swap two adjacent characters at unit cost (so "ab" → "ba" is distance 1, not 2). Recurrence gains a branch:

if i ≥ 2 and j ≥ 2 and A[i-1] == B[j-2] and A[i-2] == B[j-1]:
    dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1)

Important for spell-check because adjacent-key transpositions (“teh” for “the”) are extremely common typing errors.

9.2 Hamming Distance

Restricted variant: same length only, only substitution allowed. Computed in O(n) by counting mismatched positions. Used in error-correcting codes for fixed-length data.

9.3 Jaro and Jaro-Winkler

Different similarity metric (not a true edit distance) emphasizing matching characters within a window and prefix bonuses. Common in record linkage / entity resolution. Not what most interviews mean by “edit distance,” but sometimes asked about.

9.4 Needleman-Wunsch and Smith-Waterman

Bioinformatics alignment algorithms. Needleman-Wunsch (1970) is global alignment with arbitrary scoring matrices — equivalent to weighted edit distance. Smith-Waterman (1981) is local alignment: find the best-scoring substring alignment, useful for finding conserved motifs. Both are O(mn) DP variants.

9.5 Approximate String Matching in a Long Text

Given pattern P (length m) and text T (length n), find all positions in T where P matches with at most k edits. Naive: run edit distance from each position of T, total O(nmk). Smarter algorithms (Ukkonen 1985, bitap with errors) give O(nm) or even O(nk) for small k.

10. Common Interview Problems

ProblemLeetCode #Pattern
Edit DistanceLC 72The base problem
One Edit DistanceLC 161Special case: distance ≤ 1, O(n) greedy check
Delete Operation for Two StringsLC 583LCS-based distance variant
Minimum ASCII Delete SumLC 712Weighted version, c_del(c) = ord(c)
Distinct SubsequencesLC 115Count, not min — different DP
Word LadderLC 127BFS where neighbor = one substitution
Wildcard / Regex MatchingLC 44, 10DP table shaped like edit distance

The DP-table shape recurs in many “string alignment” problems beyond strict edit distance.

11. Pitfalls

11.1 Wrong Base Cases

dp[0][j] = j and dp[i][0] = i — not zero. Treating the empty-prefix base as zero is the most common bug; the program runs and returns numbers that are systematically too small.

11.2 Off-by-One in Indexing

Same convention as Longest Common Subsequence: dp is (m+1) × (n+1), with state (i, j) referring to the first i of A and first j of B, accessed as A[i-1] and B[j-1]. Stick to this convention rigidly.

11.3 Including Diagonal in min Even When Characters Match

When A[i-1] == B[j-1], the cost is exactly dp[i-1][j-1] (no operation needed). Some learners write dp[i][j] = min(dp[i-1][j-1], dp[i-1][j] + 1, dp[i][j-1] + 1) even on match — this is correct in value (because the diagonal will always be the minimum since insertions/deletions don’t decrease cost), but it’s misleading and slower. Use the cleaner if-else.

11.4 Forgetting Substitution Costs +1 Not +2

Substitution is one operation (atomic), not delete-then-insert (two operations). If you write dp[i-1][j-1] + 2 you’ve turned Levenshtein into LCS-distance and your answers will be too high.

11.5 Iteration Order in 1D Optimization

Like all 1D DP optimizations, the order in which you read prev[j-1] vs curr[j-1] matters. The two-row version (§4.2) is the safe default; the single-row trick (saving the diagonal in a scalar) requires care. When in doubt, use two rows — the constant-factor space difference doesn’t matter.

11.6 Reconstructing With Wrong Tie-Breaking

When multiple optimal edit scripts exist, the backtracking branch order determines which one you get. If the problem says “any optimal alignment,” any order works. If it specifies “prefer substitutions over insert+delete pairs” or “prefer trailing insertions” — order the branches accordingly.

11.7 Using Edit Distance Where Hamming Suffices

If both strings have the same length and you’re only asked about substitutions, Hamming distance is O(n) and trivial. Don’t reach for O(mn) edit distance reflexively.

11.8 Memoization Stack Depth

Long strings (m + n > 10^4) blow Python’s default recursion limit. Either sys.setrecursionlimit(...) plus OS stack adjustment, or use tabulation.

11.9 Forgetting the “ASCII Delete Sum” Twist

LC 712 asks for minimum ASCII sum of deleted characters, not minimum count. The recurrence shape is identical but the costs are character-dependent. Read the problem; don’t just pattern-match on “edit distance.”

11.10 Misclassifying Insert vs Delete from A’s Perspective

“Insert into A” decreases the gap to B; “delete from A” also decreases it but from the other side. Symbolically: dp[i][j-1] + 1 is “insert”, dp[i-1][j] + 1 is “delete”. If you swap the two semantically, the value is unchanged (it’s symmetric in the recurrence) but your reconstructed script is wrong.

12. Diagram — The 2D DP Table With Three Predecessors

flowchart LR
    TL[dp i-1, j-1] -- match: copy<br/>mismatch: substitute +1 --> C[dp i, j]
    T[dp i-1, j] -- delete A[i-1] +1 --> C
    L[dp i, j-1] -- insert B[j-1] +1 --> C

What this diagram shows. Computing dp[i][j] reads three predecessors: the diagonal dp[i-1][j-1] (used differently depending on whether the characters match — copy if equal, substitute-with-+1 if not), the cell above dp[i-1][j] (the “delete from A” option, +1), and the cell to the left dp[i][j-1] (the “insert into A” option, +1). Compared to the Longest Common Subsequence diagram, edit distance has the same three-predecessor structure but the diagonal arrow is always taken (with cost 0 or 1) rather than only on match — that’s the substitution branch. This is also why Levenshtein ≤ LCS-distance: substitution is an extra option that can never make things worse. During reconstruction, each backward step follows the arrow that was the actual minimizer at that cell, yielding the edit script in reverse.

13. Applications

13.1 Spell-Checkers and Autocorrect

The classic application. Compute edit distance from the typed word to every dictionary entry (or, more efficiently, prune via a trie + bounded-edit-distance search like the Levenshtein automaton). Suggestions are dictionary words within a small edit distance, often with weighted costs (adjacent-key substitutions are cheaper than far-key ones).

13.2 Fuzzy Matching and Record Linkage

When matching customer records across two databases, exact equality is too brittle (typos, extra spaces, transposed letters). Edit distance below a threshold is a robust similarity test. This is the core of duplicate-detection in CRM and ETL pipelines.

13.3 DNA / Protein Sequence Alignment

Bioinformatics pipelines compare gene sequences (typically thousands to millions of characters) to find conserved regions. Weighted edit distance with biochemical-similarity substitution matrices (BLOSUM62, PAM250) is the standard. BLAST and similar tools layer heuristic seeding on top of the underlying alignment DP.

13.4 Diff Algorithms

diff, git diff, and merge tools compute edit-distance-style alignments at the line level (each line treated as a single token). The Myers (1986) algorithm, used by many diff implementations, runs in O((m+n)D) where D is the actual diff size, which is small for most file changes.

13.5 Speech and OCR Post-Processing

Automatic Speech Recognition (ASR) and Optical Character Recognition (OCR) systems use edit distance against a language model to score candidate transcriptions. The Word Error Rate (WER) metric in ASR is literally edit distance at the word level.

13.6 Plagiarism Detection

Compare student submissions against each other and against online sources. Edit distance is one signal among many; sophisticated systems also look at LCS, n-gram overlap, and AST-level similarity.

14. Open Questions

  • Is there a practical sub-quadratic algorithm for similar-length strings? Ukkonen’s banded DP gives O((m+n)D), which is O(n) when D is constant — answer: yes, but only when we know D is small.
  • Why does Levenshtein dominate other edit-distance metrics in industry use? Mostly historical / convention; Damerau-Levenshtein is more accurate for typing errors, but the difference rarely matters at scale and the simpler recurrence is easier to maintain.
  • Edit distance on trees (TED — Tree Edit Distance, Tai 1979): O(n^4) classical, O(n^3) with Demaine-Mozes-Rossman-Weimann 2009. When does this come up in interviews? Almost never; mentioned for completeness.

15. See Also

Graph View

Backlinks