Edit Distance

Edit distance (Levenshtein distance) measures how many single-character operations are needed to transform one string into another. The three allowed operations are:

Insert a character
Delete a character
Replace a character

For example, the edit distance from "horse" to "ros" is 3:

Replace 'h' with 'r' → "rorse"
Delete 'r' → "rose"
Delete 'e' → "ros"

Recurrence Relation

Define dp[i][j] = minimum edit distance between word1[0..i-1] and word2[0..j-1].

Base cases:

dp[i][0] = i — delete all i characters from word1
dp[0][j] = j — insert all j characters of word2

Recurrence: If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] (characters match, no operation needed)

Else: dp[i][j] = 1 + min( dp[i-1][j], // delete word1[i-1] dp[i][j-1], // insert word2[j-1] dp[i-1][j-1] // replace word1[i-1] with word2[j-1] )

Full 2D Table Trace: "horse" → "ros"

Let's trace the entire DP table for word1 = "horse", word2 = "ros":

// Edit Distance — O(m·n) time, O(m·n) space
function minDistance(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => i === 0 ? j : j === 0 ? i : 0)
  );

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[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];
}

console.log(minDistance('horse', 'ros')); // 3
console.log(minDistance('intention', 'execution')); // 5


Table for "horse" → "ros":

      ""  r  o  s
 ""    0  1  2  3
 h     1  1  2  3
 o     2  2  1  2
 r     3  2  2  2
 s     4  3  3  2
 e     5  4  4  3

dp[5][3] = 3 ✓

Reading the table:

dp[2][2] = 1: "ho" → "ro" costs 1 (replace 'h' with 'r')
dp[3][2] = 2: "hor" → "ro" costs 2 (delete 'h', keep 'or'... or replace + delete)
dp[5][3] = 3: "horse" → "ros" costs 3

Tracing the operations backward (from dp[5][3]):

dp[5][3]=3, dp[4][3]=3 → delete 'e' from word1 (move up)
dp[4][3]=3, dp[3][2]=2 → came from replace (diagonal), 's'='s', so no-op... actually dp[3][3]=2 (diagonal) The path reveals the actual sequence of edits.

Space Optimization to O(n)

Since dp[i][j] depends only on dp[i-1][j-1], dp[i-1][j], and dp[i][j-1], we only need the previous row and one extra variable for the diagonal.

// Edit Distance — O(m·n) time, O(n) space
function minDistanceOptimized(word1, word2) {
  const m = word1.length, n = word2.length;

  // Use the shorter string as columns to minimize space
  if (m < n) return minDistanceOptimized(word2, word1);

  // prev = dp[i-1][...], initialized as dp[0][j] = j
  let prev = Array.from({ length: n + 1 }, (_, j) => j);

  for (let i = 1; i <= m; i++) {
    const curr = new Array(n + 1).fill(0);
    curr[0] = i;  // dp[i][0] = i

    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        curr[j] = prev[j - 1];  // diagonal (no-op)
      } else {
        curr[j] = 1 + Math.min(
          prev[j],      // delete (from row above)
          curr[j - 1],  // insert (from left in current row)
          prev[j - 1]   // replace (diagonal)
        );
      }
    }

    prev = curr;  // roll the row
  }

  return prev[n];
}

console.log(minDistanceOptimized('horse', 'ros')); // 3

Reconstructing the Edit Operations

To recover the actual sequence of edits, store the full table and backtrack:

// Reconstruct edit operations
function editOperations(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, (_, i) =>
    Array.from({ length: n + 1 }, (_, j) => i === 0 ? j : j === 0 ? i : 0)
  );

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
      }
    }
  }

  // Backtrack
  const ops = [];
  let i = m, j = n;
  while (i > 0 || j > 0) {
    if (i > 0 && j > 0 && word1[i-1] === word2[j-1]) {
      ops.push(`Keep '${word1[i-1]}'`);
      i--; j--;
    } else if (j > 0 && (i === 0 || dp[i][j-1] < dp[i-1][j-1] && dp[i][j-1] < dp[i][j])) {
      ops.push(`Insert '${word2[j-1]}'`);
      j--;
    } else if (i > 0 && (j === 0 || dp[i-1][j] < dp[i-1][j-1] && dp[i-1][j] <= dp[i][j-1])) {
      ops.push(`Delete '${word1[i-1]}'`);
      i--;
    } else {
      ops.push(`Replace '${word1[i-1]}' → '${word2[j-1]}'`);
      i--; j--;
    }
  }

  return ops.reverse();
}

console.log(editOperations('horse', 'ros'));
// ["Replace 'h' → 'r'", "Keep 'o'", "Delete 'r'", "Keep 's'", "Delete 'e'"]

One Edit Distance

A common variant: are two strings exactly one edit apart? You can do this in O(min(m,n)) without building the full DP table.

// One Edit Distance — O(n) time, O(1) space
function isOneEditDistance(s, t) {
  const m = s.length, n = t.length;
  if (Math.abs(m - n) > 1) return false;

  // Ensure s is the shorter (or equal) string
  if (m > n) return isOneEditDistance(t, s);

  for (let i = 0; i < m; i++) {
    if (s[i] !== t[i]) {
      if (m === n) {
        // Replace: rest of s should equal rest of t
        return s.slice(i + 1) === t.slice(i + 1);
      } else {
        // Insert into s (= delete from t): rest of s equals rest of t
        return s.slice(i) === t.slice(i + 1);
      }
    }
  }

  // All chars matched — valid only if lengths differ by exactly 1
  return m + 1 === n;
}

console.log(isOneEditDistance('ab',  'acb'));  // true  (insert 'c')
console.log(isOneEditDistance('cab', 'ad'));   // false
console.log(isOneEditDistance('1203', '1213')); // true  (replace '0' with '1')

Applications of Edit Distance

Spell checkers — suggest the word with minimum edit distance to the typo
DNA sequence alignment — insertions, deletions, substitutions in genomics
Git diff / patch — unified diff is LCS-based, conceptually related
Plagiarism detection — high edit distance suggests original work
OCR correction — fix character recognition errors in scanned text
Natural language processing — fuzzy string matching, autocomplete

Variants and Related Problems

Problem	Change from Edit Distance	Result
Delete only	Only delete ops allowed	dp[i][j] = dp[i-1][j]+1 or dp[i][j-1]+1
Insert only	Only insert ops allowed	Same as LCS (length diff = insertions)
Weighted ops	Different cost per op	Same DP, use weights in min()
One edit apart	Boolean: exactly 1 edit?	O(n) linear check
Edit distance ≤ k	Are strings within k edits?	O(k·n) with band optimization
Min deletions for LCS	Delete from both to make equal	m + n - 2·LCS(m,n)

Note

The minimum number of deletions to make two strings equal equals m + n - 2 * LCS(word1, word2). This connects edit distance (with only delete operations) directly to the LCS problem.

Tip

For competitive programming, the band optimization reduces edit distance from O(m·n) to O(k·n) when you only care whether the distance is at most k. Only compute the k diagonals around the main diagonal.