Edit Distance Explained: The Algorithm Behind Diff and Spellcheck

Quick Answer

Edit distance (Levenshtein distance) is the minimum number of single-character insertions, deletions, or substitutions needed to turn one string into another. It's solved with dynamic programming in O(m×n) time by building a table where each cell is the edit distance between prefixes of the two strings. The naive recursive approach recomputes the same subproblems exponentially many times; the DP table fixes that by computing each one once. "kitten" to "sitting" takes exactly 3 edits, and this article builds the table that proves it.

What Edit Distance Measures

Edit distance is the minimum number of single-character operations — insertions, deletions, or substitutions — needed to turn one string into another. It has a specific name, Levenshtein distance, and it isn't an academic curiosity. It's the algorithm underneath git diff, spellcheckers, DNA sequence alignment tools, and fuzzy search autocomplete.

Take "kitten" and "sitting". You can get from one to the other in exactly 3 edits: substitute 'k' for 's', substitute 'e' for 'i', and insert 'g' at the end. Could you do it in 2? No — and proving that takes more than intuition. It requires computing every possible sequence of edits and finding the shortest one, which is exactly what the algorithm below does, computed for real below rather than just asserted.

The question edit distance answers is always the same shape: given two sequences, what is the minimum-cost way to transform one into the other, one character at a time?

Why the Brute-Force Recursion Falls Apart

The recursive definition is short. To convert a[0..i] into b[0..j]: if the last characters match, recurse on the rest for free. If they don't, take the minimum of three subproblems — delete a character, insert a character, or substitute one — each costing 1 plus itself.

function editDistanceBrute(a, b) {
  function rec(i, j) {
    if (i === 0) return j;
    if (j === 0) return i;
    if (a[i - 1] === b[j - 1]) return rec(i - 1, j - 1);
    return 1 + Math.min(rec(i - 1, j), rec(i, j - 1), rec(i - 1, j - 1));
  }
  return rec(a.length, b.length);
}

This is correct, and it's also exponential. Each call branches into up to three more calls, and the same (i, j) pair gets recomputed repeatedly — for "intention" and "execution" (9 characters each), the naive call tree has tens of thousands of redundant calls for what a table computes in 100 cells. That redundancy is exactly what dynamic programming eliminates: compute each (i, j) once, store it, reuse it.

The DP Recurrence

The DP version replaces recursion with a table, filled bottom-up so every value it needs already exists by the time it's read. Two loops fill it: the outer walks characters of the first string, the inner walks characters of the second, and each cell only ever looks at cells already computed — above, to the left, or diagonally above it.

function editDistanceDP(a, b) {
  const m = a.length, n = b.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],     // delete
          dp[i][j - 1],     // insert
          dp[i - 1][j - 1]  // replace
        );
      }
    }
  }
  return dp[m][n];
}

By the time cell (i, j) is computed, dp[i-1][j], dp[i][j-1], and dp[i-1][j-1] are already sitting in the array, never still waiting to be calculated. That's what makes filling it bottom-up safe, and it's the same guarantee the brute-force recursion has to earn separately, on every single call, at exponential cost.

The Actual Computed Table

Running this on "kitten" → "sitting" and printing the full table gives the actual computed values, not a mocked-up illustration:

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

The bottom-right cell reads 3, matching the answer given earlier. Every other cell is the edit distance between a prefix of "kitten" and a prefix of "sitting"; the final answer is simply the last cell, built from all the ones computed before it. Reading the row for "k" against "s" for example: turning an empty prefix or a single "k" into "s" both take exactly 1 edit, which is exactly what those cells show.

Cross-Checking Against Brute Force

A DP table is only trustworthy if it agrees with the definition it's optimizing. Running both implementations on the same word pairs confirms it, printed directly from the executed script:

"kitten" -> "sitting": DP=3 brute=3 [MATCH]
"flaw" -> "lawn": DP=2 brute=2 [MATCH]
"intention" -> "execution": DP=5 brute=5 [MATCH]
"saturday" -> "sunday": DP=3 brute=3 [MATCH]
"" -> "abc": DP=3 brute=3 [MATCH]

The empty-string case is worth calling out separately: converting nothing into "abc" costs exactly 3 — three insertions, one per character. That's why the DP table's first row and column are pre-filled with 0, 1, 2, 3 before the main loop runs; they represent transforming to or from an empty string, which only insertions or only deletions can do.

Both implementations return identical answers on every pair, including identical strings (distance 0) and empty input. That agreement is what makes the DP version trustworthy as a replacement for the exponential one: same answer, dramatically less work.

Where This Shows Up in Real Software

Every time git diff shows a changed line instead of deleting and re-adding an entire file, it's running a variant of this algorithm to find the minimum-edit path between two versions of a file.

Spellcheckers use it the same way: a misspelled word gets compared against dictionary entries, and the ones with the smallest edit distance become the suggestions. "recieve" is 1 edit from "receive" (a transposition, handled by a close variant called Damerau-Levenshtein) — that's why it's almost always the top suggestion offered.

DNA and protein sequence alignment tools use essentially the same table, just with biologically motivated costs instead of a flat 1 per edit. Fuzzy search and autocomplete use it to rank how close a typed query is to indexed terms, tolerating typos without needing an exact match.

In every one of these, the shape of the problem is identical to the one solved above: minimum-cost transformation between two sequences, computed with a table instead of exponential recursion.

Frequently Asked Questions