Edit Distance

Dynamic Programming

avgO(m·n)worstO(m·n)spaceO(m·n)

Cell [i][j] will hold the fewest edits that turn the first i letters of "KITTEN" into the first j letters of "SITTING"

1 / 54

Code

function editDistance(a: string, b: string) {  const m = a.length, n = b.length;  const dp: number[][] = Array.from({ length: m + 1 }, () => new Array(n + 1));  for (let j = 0; j <= n; j++) dp[0][j] = j;  for (let i = 1; 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]);    }  }  let i = m, j = n;  const ops: string[] = [];  while (i > 0 || j > 0) {    if (i > 0 && j > 0 && a[i - 1] === b[j - 1]) {      ops.unshift(`keep ${a[i - 1]}`); i--; j--;    } else if (i > 0 && j > 0 && dp[i][j] === dp[i - 1][j - 1] + 1) {      ops.unshift(`substitute ${a[i - 1]} → ${b[j - 1]}`); i--; j--;    } else if (i > 0 && dp[i][j] === dp[i - 1][j] + 1) {      ops.unshift(`delete ${a[i - 1]}`); i--;    } else {      ops.unshift(`insert ${b[j - 1]}`); j--;    }  }  return { distance: dp[m][n], ops };}

procedure editDistance(A, B)  m ← |A|; n ← |B|  dp ← (m + 1) × (n + 1) table  for j ← 0 to n do dp[0][j] ← j    ▷ j inserts  for i ← 1 to m do dp[i][0] ← i    ▷ i deletes  for i ← 1 to m do    for j ← 1 to n do      if A[i] = B[j] then dp[i][j] ← dp[i − 1][j − 1]    ▷ free match      else dp[i][j] ← 1 + min(dp[i − 1][j − 1], dp[i − 1][j], dp[i][j − 1])    ▷ substitute, delete, insert    end for  end for  i ← m; j ← n    ▷ walk back from the corner  ops ← empty list  while i > 0 or j > 0 do    if i > 0 and j > 0 and A[i] = B[j] then      prepend "keep A[i]"; i ← i − 1; j ← j − 1    else if i > 0 and j > 0 and dp[i][j] = dp[i − 1][j − 1] + 1 then      prepend "substitute A[i] → B[j]"; i ← i − 1; j ← j − 1    else if i > 0 and dp[i][j] = dp[i − 1][j] + 1 then      prepend "delete A[i]"; i ← i − 1    else      prepend "insert B[j]"; j ← j − 1    end if  end while  return dp[m][n], opsend procedure

Variables

m=6n=7

Counters

cells filled: 0

How it works

Counts the fewest single-letter inserts, deletes and substitutions that turn one string into another (Levenshtein distance). Cell [i][j] holds the cost for the first i letters of a and the first j letters of b: matching letters cost nothing, otherwise pay 1 plus the cheapest neighbouring cell. Walking back from the corner spells out the edits.

Complexity

Best: O(m·n)
Average: O(m·n)
Worst: O(m·n)
Space: O(m·n)

Edit Distance

How it works

Complexity

Search algorithms