A typeahead ranks catalog tokens against the query. Equal-length names get a Hamming pass: count positions that differ. flaw versus lawn scores four — “unrelated.” A shopper types kiten for kitten. Hamming refuses: the lengths differ. Someone pads the short string. Someone writes a recursive insert / delete / substitute explorer. Two five-letter tokens compile. A SKU field against a pasted query of length forty does not.

Levenshtein fills a costed grid: each cell is the cheapest way to turn one prefix into the other with insert, delete, or substitute. Unit cost unless you say otherwise — each operation is 1. You do not enumerate alignments. You fill prefixes. After the last cell you have a number; walking the grid gives one script that achieves it.

This post is that grid and one recovery walk. Families and the catalog live on the Algorithms Roadmap. Hamming is equal length and substitute-only — not this. LCS is the same family of prefix tables and a different job: longest shared subsequence, not cheapest edits. This lab does not reconstruct LCS.

Hamming, or every alignment

Hamming is defined only when |a| == |b|. It counts substitutions, nothing else. flaw and lawn are the same length, so Hamming is legal — and it reports 4 because every position mismatches. Two edits fix them: delete f, insert n. Padding a shorter string and then running Hamming is one alignment, not the minimum over inserts and deletes.

The recursive explorer is the other trap: at each pair of suffixes, try substitute, try delete, try insert. Overlapping prefixes repeat. Short demos finish. Production lengths do not.

Equal-length mismatch count is Hamming. Padding is not Levenshtein. The move is to throw the alignments away and keep a table of prefix costs.

The cell: prefixes of a and of b

Index i as the length of a prefix of source a, j as the length of a prefix of target b. Then dp[i][j] is the min cost to turn a[0..i) into b[0..j).

Initialize from the empty prefixes:

  • dp[0][j] = j — insert each character of b’s prefix into empty a.
  • dp[i][0] = i — delete each character of a’s prefix to reach empty b.

For i > 0, j > 0:

matchOrSub = dp[i-1][j-1] + (a[i-1] == b[j-1] ? 0 : 1)
delete     = dp[i-1][j] + 1     // drop a[i-1]
insert     = dp[i][j-1] + 1     // add b[j-1]
dp[i][j]   = min(matchOrSub, delete, insert)

A match copies the diagonal. A mismatch takes 1 plus the cheapest of substitute, delete, or insert. After i = |a| and j = |b|, dp[n][m] is the distance.

Note: This post uses unit costs. Changing an operation’s cost changes the numbers, not the shape of the table. Affine gaps and weighted biology alignments are cousins with extra state — not this fill.

A walk: flaw → lawn

Source a = "flaw" (rows), target b = "lawn" (columns). Hamming would print 4. The grid prints 2.

      ε  l  a  w  n
   ε  0  1  2  3  4
   f  1  1  2  3  4
   l  2  1  2  3  4
   a  3  2  1  2  3
   w  4  3  2  1  2

dp[4][4] = 2

First row is inserts into empty source: ε → l, ε → la, … First column is deletes down to empty target. dp[1][1] is f versus l: mismatch, 1 + min(1, 1, 0) = 1 (substitute). dp[2][1] is l versus l: match, copy dp[1][0] = 1. dp[3][2] is a versus a: match, copy 1. dp[4][3] is w versus w: match, copy 1. The last cell w versus n is a mismatch: 1 + min(delete 3, insert 1, substitute 2) = 2 — insert n.

Empty source or empty target never needs a special case beyond that first row and column. ("", "car") is 3 inserts. ("car", "") is 3 deletes.

Java: fill the grid

There is no String.editDistance in the JDK. The roadmap’s map lists sorts, binary search, shuffle, and queues. This job is a table you allocate.

static int levenshtein(String a, String b) {
    int n = a.length();
    int m = b.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 0; i <= n; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= m; j++) {
        dp[0][j] = j;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            int matchOrSub = dp[i - 1][j - 1]
                    + (a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1);
            int delete = dp[i - 1][j] + 1;
            int insert = dp[i][j - 1] + 1;
            dp[i][j] = Math.min(matchOrSub, Math.min(delete, insert));
        }
    }
    return dp[n][m];
}

On the walk, levenshtein("flaw", "lawn") returns 2. Swap the arguments and you get the same number — unit insert and delete are symmetric. The alignment you recover below is not unique; the cost is.

Note: Distances are at most n + m, so int is enough. If you only need the number, two rolling rows of length m + 1 drop extra space to O(m). Recovery needs the full grid or predecessor pointers — do not throw the table away and then hope to reconstruct a script from the integer.

Recover one alignment

Dashboards want the script, not only 2. Walk from dp[n][m] to dp[0][0]. Prefer a diagonal step when it explains the cell; otherwise insert (left) or delete (up). Ties pick one legal parent — that is enough for “one alignment.”

static String[] align(String a, String b, int[][] dp) {
    int i = a.length();
    int j = b.length();
    StringBuilder ga = new StringBuilder();
    StringBuilder gb = new StringBuilder();
    while (i > 0 || j > 0) {
        if (i > 0 && j > 0
                && dp[i][j] == dp[i - 1][j - 1]
                && a.charAt(i - 1) == b.charAt(j - 1)) {
            ga.append(a.charAt(i - 1));
            gb.append(b.charAt(j - 1));
            i--;
            j--;
        } else if (i > 0 && j > 0
                && dp[i][j] == dp[i - 1][j - 1] + 1) {
            ga.append(a.charAt(i - 1));
            gb.append(b.charAt(j - 1));
            i--;
            j--;
        } else if (j > 0 && dp[i][j] == dp[i][j - 1] + 1) {
            ga.append('-');
            gb.append(b.charAt(j - 1));
            j--;
        } else {
            ga.append(a.charAt(i - 1));
            gb.append('-');
            i--;
        }
    }
    return new String[] { ga.reverse().toString(), gb.reverse().toString() };
}

On the walk, the parents are insert n, then three matches law, then delete f:

flaw-
-lawn

That is delete f and insert n. Cost 2. Hamming’s four substitutions are a different, more expensive script. Strict diagonal-first keeps the earliest parent on a tie; if you need a longest match run among equals, change the walk, not the fill.

Note: Returning only the integer and then searching for any pair of strings at that distance can disagree on ties and re-pays a search the table already did. If you need the script, keep the grid and walk it.

LCS also fills an (n+1) × (m+1) prefix table. The recurrence looks like a cousin: match extends a shared subsequence; a skip on either side does not. The question is different. LCS maximizes how much you can keep, in order, not necessarily contiguous. Levenshtein minimizes how much you must change.

If substitute is forbidden — only insert and delete — the distance is |a| + |b| - 2 · LCS(a, b): delete what is not in the common subsequence, insert the rest of b. Unit substitute breaks that identity, because one replace can be cheaper than delete-plus-insert. Do not reconstruct LCS in this lab. If the ticket is “longest shared subsequence,” open that post and fill that table.

Same family of prefix grids. Different objective. Different walk.

Complexity

WhatCostWhy
TimeO(n m)One visit per prefix pair; min of three is O(1)
Extra space (distance)O(n m), or O(min(n, m))Full table, or two rolling rows if you drop recovery
Extra space (alignment)O(n m)Need the grid (or predecessors) to walk a script
Naive recursionExponentialOverlapping prefix pairs with no table
HammingO(n)Equal length, substitutions only — a different spec
OutputO(1) or O(n + m)The integer, or two gapped strings of length at most n + m

The input strings are whoever owns them. The procedure is the fill; the script is a walk, not a second search. A correct recursive explorer is still the wrong default on SKU-length tokens.

When not to use this grid

Skip the n × m table when the job is not “minimum insert / delete / substitute cost between two strings.”

  • Hamming is the spec. Fixed-width codes, checksums, equal-length blocks: count substitutions. Do not allocate a Levenshtein table to answer a positional mismatch count. Lengths must match; if they do not, Hamming is undefined, not “pad and hope.”
  • You needed LCS, not edits. Shared subsequence (diff-as-keep, plagiarism-as-overlap, the LCS identity above without substitute) is LCS. Reconstructing that subsequence is that post’s walk.
  • You are ranking a corpus. One pair is O(n m). A query against millions of catalog rows is not “loop Levenshtein.” Bounded-k automata, indexes, and search libraries exist so you do not cube a storefront. This post is the pair, not a fuzzy-search product.
  • A fourth operation is in the spec. Damerau adds adjacent transposition. Spellcheck likes it. It is not the three-op recurrence above. Do not sneak a swap into the min and still call the result Levenshtein.
  • You only needed equality. String.equals / Arrays.equals. Distance 0 versus > 0 does not justify the table.
  • The cost model is not unit operations. Weighted matches, affine gaps, or banded O(k n) variants for a small distance bound are different bills. Quote O(n m) only for the dense unit fill.

Two strings, unit insert / delete / substitute, one cost (and optionally one script) — that is the job. Anything else is a different procedure that may call this fill.

Cheat sheet

Job:         min insert / delete / substitute cost (Levenshtein)
Cell:        dp[i][j] = cost to turn a[0..i) into b[0..j)
Init:        dp[i][0] = i; dp[0][j] = j
Recurrence:  min(diag + 0/1, delete + 1, insert + 1)
Answer:      dp[n][m]
Alignment:   walk from (n, m) to (0, 0); one legal parent on ties
Time/space:  O(n m) / O(n m)  (O(min(n,m)) extra if distance only)
JDK:         none — allocate the table
Not this:    Hamming, LCS reconstruction, corpus fuzzy search, Damerau

Do:

  • Initialize the first row and column as inserts and deletes of whole prefixes.
  • Name unit costs at the method boundary if a caller might expect weighted ops.
  • Keep the grid (or predecessors) when the caller needs a script, not only the integer.
  • Point LCS tickets at the LCS table — related family, different objective.

Don’t:

  • Pad to equal length and call Hamming Levenshtein.
  • Recurse on suffixes without a table once n and m are SKU-sized.
  • Reconstruct an LCS as the main lab and claim you taught edit distance.
  • Quote O(n m) for a corpus ranker or a search-library fuzziness setting.

Wrap-up

Levenshtein replaces “every alignment” with one cell per prefix pair: match or substitute on the diagonal, delete a source character, or insert a target character. The first row and column are the empty-prefix bills. The last cell is the distance. One walk of the grid is one script — flaw- over -lawn costs 2, not Hamming’s four.

The layout is a dense table of prefixes. The procedure is this fill. When you need the script, walk the parents you already computed. When the job is Hamming, LCS, or ranking a storefront, this grid is the wrong named procedure — start from the Algorithms Roadmap and pick the job again.

Next optional step in the series Build a prefix code from symbol frequencies with a heap — greedy, not a DP grid. Huffman Coding: Build a Prefix Code From Frequencies