Levenshtein distance
JavaScript, String, Algorithm · Dec 29, 2020
Calculates the difference between two strings, using the Levenshtein distance algorithm.
- If either of the two strings has a
lengthof zero, return thelengthof the other one. - Use a
forloop to iterate over the letters of the target string and a nestedforloop to iterate over the letters of the source string. - Calculate the cost of substituting the letters corresponding to
i - 1andj - 1in the target and source respectively (0if they are the same,1otherwise). - Use
Math.min()to populate each element in the 2D array with the minimum of the cell above incremented by one, the cell to the left incremented by one or the cell to the top left incremented by the previously calculated cost. - Return the last element of the last row of the produced array.
const levenshteinDistance = (s, t) => {
if (!s.length) return t.length;
if (!t.length) return s.length;
const arr = [];
for (let i = 0; i <= t.length; i++) {
arr[i] = [i];
for (let j = 1; j <= s.length; j++) {
arr[i][j] =
i === 0
? j
: Math.min(
arr[i - 1][j] + 1,
arr[i][j - 1] + 1,
arr[i - 1][j - 1] + (s[j - 1] === t[i - 1] ? 0 : 1)
);
}
}
return arr[t.length][s.length];
};levenshteinDistance('duck', 'dark'); // 2
