[TypeScript] Levenshtein Distance

levenshtein-distance.ts

/**
 * This is a simple and performant implementation of
 * the Wagner–Fischer algorithm for computing
 * the Levenshtein Distance between two strings.
 *
 * It is based on the observation that we can reserve a matrix
 * to hold the Levenshtein distances between all prefixes of
 * the first string and all prefixes of the second.
 *
 * Then we can compute the values in the matrix
 * by flood filling the matrix, and thus find the distance
 * between the two full strings as the last value computed.
 */
export function levenshteinDistance(first: string, second: string): number {
    const dist: number[][] = [];

    for (let i = 0; i <= first.length; i++) {
        dist[i] = [i];
    }

    for (let j = 0; j <= second.length; j++) {
        dist[0][j] = j;
    }

    for (let i = 1; i <= first.length; i++) {
        for (let j = 1; j <= second.length; j++) {
            const comparativeDistance = first[i - 1] === second[j - 1] ? 0 : 1;

            const minAdjacentDistance = Math.min(
                dist[i - 1][j - 1],
                dist[i - 1][j],
                dist[i][j - 1]
            );

            dist[i][j] = minAdjacentDistance + comparativeDistance;
        }
    }

    return dist[first.length][second.length];
}