Levenshtein edit distance solution using DP

levenshtein_edit_distance.ts

const COLLATOR = Intl.Collator('generic', {sensitivity: 'base'})

export function levenshteinEditDistance(
  source: string,
  target: string,
): number {
  if (source.length === 0 || target.length === 0) {
    return 0
  }

  // [0, ..., N]
  const previousRow = new Array<number>(target.length + 1)
  for (let i = 0; i < target.length + 1; i++) {
    previousRow[i] = i
  }
  previousRow[target.length] = target.length

  for (let i = 0; i < source.length; i++) {
    let nextDistance = i + 1

    for (let j = 0; j < target.length; j++) {
      let currentDistance = nextDistance

      const areCharCodesEqual =
        COLLATOR.compare(source.charAt(i), target.charAt(j)) === 0

      const distanceIfSubstitute = previousRow[j] + (areCharCodesEqual ? 0 : 1)
      const distanceIfInsert = currentDistance + 1
      const distanceIfDelete = previousRow[j + 1] + 1

      nextDistance = Math.min(
        distanceIfSubstitute,
        distanceIfInsert,
        distanceIfDelete,
      )

      previousRow[j] = currentDistance
    }

    previousRow[target.length] = nextDistance
  }

  return previousRow[target.length]
}