Javascript find edit distance not returning correct value

Question

I'm working on a function that computes the edit distance of two strings but according to this only calculator Im getting an incorrect value. Im getting 19 and the calculator is returning 7. Im not sure whats wrong with my program I based it off of The Algorithm Design Manual.

var recFindEditDistance = function(P, T, i, j) {
    if (i === undefined || j === undefined) return recFindEditDistance(P, T, P.length - 1, T.length - 1);
    if (i === 0 && j === 0) return 0;
    if (i === 0) return j;
    if (j === 0) return i;

    var sub = recFindEditDistance(P, T, i-1, j-1) + (P[i]===T[j] ? 0 : 1);
    var del = recFindEditDistance(P, T, i, j-1) + 1;
    var add = recFindEditDistance(P, T, i-1, j) + 1;

    return Math.max(sub, add, del);
};

console.log(recFindEditDistance('ffadsfsadfasf', 'asdfasdf'));

Answer 1

Levenshtein distance algorithm at the every position tries to achieve the minimum distance to get to the next position.

At the same time, you are trying to get the maximum one :)

Simply change

return Math.max(sub, add, del);

to

return Math.min(sub, add, del);

And it will work :)

Demo:

function recFindEditDistance(P, T, i, j) {
    if (i === undefined || j === undefined) return recFindEditDistance(P, T, P.length - 1, T.length - 1);
    if (i === 0 && j === 0) return 0;
    if (i === 0) return j;
    if (j === 0) return i;

    var sub = recFindEditDistance(P, T, i-1, j-1) + (P[i]===T[j] ? 0 : 1);
    var del = recFindEditDistance(P, T, i, j-1) + 1;
    var add = recFindEditDistance(P, T, i-1, j) + 1;

    return Math.min(sub, add, del);
};

document.body.innerText = recFindEditDistance('ffadsfsadfasf', 'asdfasdf');