edit distance: counting the minimum number of operations required to transform one string into the other.

editDistance.js

'use strict'

/**
 * note: substitute costs 2
 *
 * if either string is empty => length of the other
 * if the last chars of both match =>
 *   recursively call edit without adding distance
 * if not =>
 *   Math.min of three ways
 */
function editDistance (str1, str2) {
  const len1 = str1.length
  const len2 = str2.length

  return recur(str1, str2, len1, len2)

  function recur (str1, str2, len1, len2) {
    if (len1 === 0) {
      return len2
    }

    if (len2 === 0) {
      return len1
    }

    if (str1[len1] === str2[len2]) {
      return recur(str1, str2, len1 - 1, len2 - 1)
    }

    return Math.min(
      recur(str1, str2, len1, len2 - 1) + 1,
      recur(str1, str2, len1 - 1, len2) + 1,
      recur(str1, str2, len1 - 1, len2 - 1) + 2
    )
  }
}

/**
 * DP: see the DP diagram
 * https://web.stanford.edu/class/cs124/lec/med.pdf
 */
function editDistance (str1, str2) {
  const len1 = str1.length
  const len2 = str2.length
  let d = []

  for (let i = 0; i <= len1; i++) {
    d[i] = []
    d[i][0] = i
  }

  for (let j = 0; j <= len2; j++) {
    d[0][j] = j
  }

  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      const cost = str1[i - 1] === str2[j - 1] ? 0 : 2

      d[i][j] = Math.min(
        d[i - 1][j] + 1,
        d[i][j - 1] + 1,
        d[i - 1][j - 1] + cost
      )
    }
  }

  return d[len1][len2]
}