Edit distance

O(m·n)

Edit distance, or Levenshtein distance, measures how different two strings are: it's the minimum number of single-character insertions, deletions, and substitutions needed to transform one into the other. A dynamic-programming table dp[i][j] holds the distance between the first i characters of A and the first j of B. Each cell builds on three neighbours — the value above, to the left, and diagonally up-left — so the whole table fills in O(m·n). The bottom-right corner is the answer. It powers spell-checkers, diff tools, and fuzzy search.

DP table
Press ▶ to run
Edit the input and press Play

How it works

  1. Fill the first row and column with 0,1,2,… — the cost of building one string from nothing.
  2. For each cell, if the two characters match, copy the diagonal value (no edit needed).
  3. Otherwise take 1 + the smallest of the cell above, left, and diagonal (delete, insert, substitute).
  4. The bottom-right cell holds the edit distance between the full strings.

Pseudocode

1editDistance(a, b):                 # O(m·n)2  dp[i][0] ← i,  dp[0][j] ← j        # base: delete / insert all3  for i in 1..m, j in 1..n:4    if a[i-1] = b[j-1]:5      dp[i][j] ← dp[i-1][j-1]        # chars match, no cost6    else:7      dp[i][j] ← 1 + min(8        dp[i-1][j],                  # delete9        dp[i][j-1],                  # insert10        dp[i-1][j-1])                # substitute11  return dp[m][n]