Levenshtein Distance

var cache = {}
var counter = 0

// Function to calculate levenshtein distance
function minDist(string1, string2) {
    if(cache[string1] && cache[string1][string2])
        return cache[string1][string2]

    if(!string1.length)
        return cache_score(string1, string2, string2.length)
    if(!string2.length)
        return cache_score(string1, string2, string1.length)

    var string1Shorter = string1.substring(0, string1.length - 1)
    var string2Shorter = string2.substring(0, string2.length - 1)

    // Addition case
    var add_score = minDist(string1, string2Shorter) + 1

    // Subtraction case
    var subt_score = minDist(string1Shorter, string2) + 1

    // Substitution case
    var cost = string1[string1.length - 1] == string2[string2.length - 1]  ?  0 : 1

    console.log(string1, string2, string1Shorter, string2Shorter, cost);

    var subs_score = minDist(string1Shorter, string2Shorter) + cost
    var score = Math.min(add_score, subt_score, subs_score)

    counter += 1
    //console.log("converting", string1, "to", score)
    return cache_score(string1, string2, score)
}

function cache_score(string1, string2, score){
    if(!cache[string1])
        cache[string1] = {}

    if(!cache[string1][string2])
        cache[string1][string2] = score
    
    return score
}

console.log("distance is: ", minDist("ffellato", "jellato"), counter)