/**
 * A method for fuzzy matching strings.
 * TODO: Optimize the space used. Currently uses NxM. can be reduced to N+M.
 * @param {string} str0
 * @param {string} str1
 * @returns {number} The number of edits needed to change one string to another.
 */
export function levenshteinDistance(str0: string, str1: string): number {
  if (str0 === null || str1 === null) throw Error('No null arguments.');

  if (str0 === '' && str1 === '') return 0;

  const str0Length: number = str0.length + 1;
  const str1Length: number = str1.length + 1;

  // Initialize arrays
  const distances: Array<Array<number>> = new Array<Array<number>>(str0Length);
  for (let i = 0; i < str0Length; i++) {
    distances[i] = new Array<number>(str1Length);
  }
  // Set initial values
  for (let i = 0; i < str0Length; i++) {
    distances[i][0] = i;
  }
  // Set initial values
  for (let i = 0; i < str1Length; i++) {
    distances[0][i] = i;
  }

  for (let j = 1; j < str1Length; j++) {
    for (let i = 1; i < str0Length; i++) {
      let subCost: number;
      if (str1[j - 1] === str0[i - 1]) {
        subCost = 0;
      } else {
        subCost = 1;
      }

      distances[i][j] = Math.min(
        distances[i - 1][j] + 1,
        distances[i][j - 1] + 1,
        distances[i - 1][j - 1] + subCost
      );
    }
  }

  return distances[str0Length - 1][str1Length - 1];
}