Edit Distance (Levenshtein)

Edit distance (Levenshtein distance) between two strings s and t is the minimum number of single-character edits — insertions, deletions, or substitutions — needed to transform s into t. It powers spell checkers, fuzzy search, and DNA alignment.

State and Recurrence

State: dp[i][j] = edit distance between s[0..i-1] and t[0..j-1].

Recurrence:

• If s[i-1] === t[j-1]: dp[i][j] = dp[i-1][j-1] (no edit needed)
• Otherwise: dp[i][j] = 1 + min(
  • dp[i-1][j] — delete from s (or insert into t)
  • dp[i][j-1] — insert into s (or delete from t)
  • dp[i-1][j-1] — substitute s[i-1] with t[j-1]
  • )

Base cases:

• dp[0][j] = j — transforming empty string to t[0..j-1] requires j insertions
• dp[i][0] = i — transforming s[0..i-1] to empty string requires i deletions

function editDistance(s, t) {
  const m = s.length, n = t.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 (s[i - 1] === t[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]    // substitute
        );
      }
    }
  }
  return dp[m][n];
}

console.log(editDistance('kitten', 'sitting')); // 3
// kitten → sitten (substitute k→s)
// sitten → sittin (substitute e→i)
// sittin → sitting (insert g)

Space-Optimized Version

Row i depends only on row i-1, so a rolling pair of arrays reduces space from O(mn) to O(n):

function editDistanceOpt(s, t) {
  const m = s.length, n = t.length;
  let prev = Array.from({ length: n + 1 }, (_, j) => j);

  for (let i = 1; i <= m; i++) {
    const curr = new Array(n + 1);
    curr[0] = i;
    for (let j = 1; j <= n; j++) {
      if (s[i - 1] === t[j - 1]) {
        curr[j] = prev[j - 1];
      } else {
        curr[j] = 1 + Math.min(prev[j], curr[j - 1], prev[j - 1]);
      }
    }
    prev = curr;
  }
  return prev[n];
}

console.log(editDistanceOpt('sunday', 'saturday')); // 3

Reading the Table

Each cell represents a subproblem. The three neighbors of dp[i][j] are:

Backtracking from dp[m][n] to dp[0][0] reveals the sequence of operations, similar to LCS reconstruction.

Complexity

Time O(mn), space O(mn) with full table, O(n) with rolling rows.

Up Next

Coin change applies 1-D DP to find the fewest coins for a target amount and shows why greedy fails for arbitrary coin systems.