Levenshtein Edit Distance With Backtrace

export function editDistance(source, target, options = {}) {
  if (typeof source !== "string" || typeof target !== "string") {
    throw new TypeError("source and target must be strings");
  }
  const { maxLength = 4000 } = options;
  const left = Array.from(source);
  const right = Array.from(target);
  if (left.length > maxLength || right.length > maxLength) {
    throw new RangeError(`input exceeds maxLength of ${maxLength} code points`);
  }
  const rows = left.length + 1;
  const columns = right.length + 1;
  const matrix = Array.from({ length: rows }, () => new Uint32Array(columns));
  for (let row = 0; row < rows; row += 1) matrix[row][0] = row;
  for (let column = 0; column < columns; column += 1) matrix[0][column] = column;
  for (let row = 1; row < rows; row += 1) {
    for (let column = 1; column < columns; column += 1) {
      const cost = left[row - 1] === right[column - 1] ? 0 : 1;
      matrix[row][column] = Math.min(
        matrix[row - 1][column] + 1,
        matrix[row][column - 1] + 1,
        matrix[row - 1][column - 1] + cost,
      );
    }
  }
  return {
    distance: matrix[rows - 1][columns - 1],
    operations: backtrace(left, right, matrix),
  };
}

function backtrace(left, right, matrix) {
  const operations = [];
  let row = left.length;
  let column = right.length;
  while (row > 0 || column > 0) {
    const diagonalCost = row > 0 && column > 0 && left[row - 1] === right[column - 1] ? 0 : 1;
    if (row > 0 && column > 0 && matrix[row][column] === matrix[row - 1][column - 1] + diagonalCost) {
      if (diagonalCost === 1) {
        operations.push({ type: "substitute", from: left[row - 1], to: right[column - 1] });
      }
      row -= 1;
      column -= 1;
    } else if (row > 0 && matrix[row][column] === matrix[row - 1][column] + 1) {
      operations.push({ type: "delete", value: left[row - 1] });
      row -= 1;
    } else {
      operations.push({ type: "insert", value: right[column - 1] });
      column -= 1;
    }
  }
  return operations.reverse();
}

console.log(editDistance("kitten", "sitting"));
console.log(editDistance("book", "back"));
console.log(editDistance("", "abc"));