Calculate Levenshtein distance (a.k.a. edit distance) between two strings

levenshtein_distance.js

'use strict';

/*
    Calculate Levenshtein distance(edit dstance) between str1 and str2.
*/
const calculateLevenshteinDistance = (str1, str2) => {
    // Initialize distance table
    let distanceTable = new Array(str1.length + 1);
    for (let row = 0; row < str1.length + 1; row++) {
        distanceTable[row] = new Array(str2.length + 1);
    }

    // Store distances from empty string (1st row and column)
    for (let row = 0; row < str1.length + 1; row++) {
        distanceTable[row][0] = row;
    }
    for (let col = 0; col < str2.length + 1; col++) {
        distanceTable[0][col] = col;
    }

    // Fill table by smallest distance
    for (let row = 1; row < str1.length + 1; row++) {
        for (let col = 1; col < str2.length + 1; col++) {
            const replaceCost = (str1.charAt(row - 1) === str2.charAt(col - 1)) ? 0 : 1;
            distanceTable[row][col] = Math.min(
                distanceTable[row - 1][col] + 1,                // insert
                distanceTable[row][col - 1] + 1,                // delete
                distanceTable[row - 1][col - 1] + replaceCost   // replace
            );
        }
    }

    printTable(str1, str2, distanceTable);
    return distanceTable[str1.length][str2.length];
}

/*
    get pritty output
*/
const printTable = (str1, str2, table) => {
    // Print str2 on horizontal
    let firstLine = '  ';
    for (let col = 0; col < str2.length + 1; col++) {
        if (col === 0) {
            firstLine += '  ';        
        } else {
            const widthFixed = ('  ' + str2.charAt(col - 1)).slice(-2);
            firstLine += widthFixed;
        }
    }
    console.log(firstLine);
    
    // Print split line
    console.log('--'.repeat(str2.length + 2));
    
    for (let row = 0; row < str1.length + 1; row++) {
        // Print str1 on vertical
        let line = (row === 0) ? ' |' : (str1.charAt(row - 1) + '|');
        // Print contents of table
        for (let col = 0; col < str2.length + 1; col++) {
            const widthFixed = ('  ' + table[row][col]).slice(-2);
            line += widthFixed;
        }
        console.log(line);
    }
};

/*
    main routine
*/

if (process.argv.length < 4) {
    console.log('usage: node levenshtein.js str1 str2');
    process.exit(1);
}

const str1 = process.argv[2];
const str2 = process.argv[3];

console.log('distance=' + calculateLevenshteinDistance(str1, str2));