Edit distance (Levenshtein, recursion)

Hard TimeO(3^(m+n)) naive; O(m·n) memoised SpaceO(m + n) stack

Return the fewest single-character edits — insert, delete or substitute — that turn one string into another. "cat" to "cut" takes 1. Each edit costs one wherever it is applied, turning a string into itself costs nothing, and turning any string into an empty one costs its length.

Examples

Example 1

Input
a = 'cat'b = 'cut'i = 0j = 0
Output
1
One substitution, a for u; the c and the t already match.

Example 2

Input
a = 'cat'b = ''i = 0j = 0
Output
3
Three characters to delete, and nothing cheaper exists — the cost is the length.

The Code

function editDistance(a, b, i, j) {
  if (i === a.length) return b.length - j;
  if (j === b.length) return a.length - i;
  if (a[i] === b[j]) return editDistance(a, b, i + 1, j + 1);
  const insert = editDistance(a, b, i, j + 1);
  const remove = editDistance(a, b, i + 1, j);
  const replace = editDistance(a, b, i + 1, j + 1);
  return 1 + Math.min(insert, remove, replace);
}
editDistance('cat', 'cut', 0, 0);
Done

The first 10 calls, of 14. This one does not fit on a page.

Step through editDistance('cat', 'cut', 0, 0) call by call

More like this

All dynamic programming examples (20) →