Javascript find edit distance not return correct value

Question

Я работаю над функцией, которая вычисляет расстояние редактирования двух строк, но в соответствии с этим калькулятором Im получает неправильное значение. Я получаю 19, а калькулятор возвращается 7. Я не уверен, что случилось с моей программой, на которой я основал ее Руководство по разработке алгоритма.

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

Левенштейна алгоритм на каждой позиции пытается достичь минимального расстояние, чтобы добраться до следующей позиции.

В то же время, вы пытаетесь получить максимум один :)

Просто измените

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

в

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

И это будет работать:)

Демо:

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');