Edit Distance

Levenshtein distance through a two-dimensional DP table

Count the cheapest string transformation

Edit distance is the minimum number of single-character insertions, deletions, and substitutions needed to transform one string into another. Define dp[i][j] as the cost of transforming the first i source characters into the first j target characters.

Each cell represents three possible edits

The first row counts insertions from an empty source, and the first column counts deletions to an empty target. If the current characters match, copy the top-left cell. Otherwise take 1 plus the minimum of top-left for substitution, up for deletion, and left for insertion.

The player transforms SAT into SUN. The amber cell is being solved, yellow cells supply candidate costs, and the new value turns green. The bottom-right cell is the answer for both complete strings.

	∅	S	U	N
∅	0	1	2	3
S	1
A	2
T	3

Initialize the first row with insertion counts and the first column with deletion counts.

1function editDistance(a: string, b: string): number {
const m = a.length, n = b.length;
const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
for (let j = 0; j <= n; j++) dp[0][j] = j;
for (let i = 0; i <= m; i++) dp[i][0] = i;
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 - 1], dp[i - 1][j], dp[i][j - 1]);
    }
  }
}
return dp[m][n];
17}

SourceSAT

TargetSUN

1 / 11

Complexity and reconstruction

Filling an (m + 1) x (n + 1) table costs O(mn) time and O(mn) space. If only the distance is needed, two rows reduce auxiliary space to O(n). Keeping the full table allows a backward trace of the actual edits.

Applications include spell checking, fuzzy search, text comparison, and biological sequence alignment.

Compare the three-neighbor minimum with the matching recurrence in Longest Common Subsequence.

Algorithm Visualizer

Edit Distance

Count the cheapest string transformation

Each cell represents three possible edits

Complexity and reconstruction