# 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 `length` of zero, return the `length` of the other one.
• Use a `for` loop to iterate over the letters of the target string and a nested `for` loop to iterate over the letters of the source string.
• Calculate the cost of substituting the letters corresponding to `i - 1` and `j - 1` in the target and source respectively (`0` if they are the same, `1` otherwise).
• 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`

### Written by Angelos Chalaris

I'm Angelos Chalaris, a JavaScript software engineer, based in Athens, Greece. The best snippets from my coding adventures are published here to help others learn to code.

If you want to keep in touch, follow me on GitHub or Twitter.

## More like this

• ### CSV to JSON

Converts a comma-separated values (CSV) string to a 2D array of objects. The first row of the string is used as the title row.

JavaScript, String · Jan 30, 2022

• ### Index of substrings

Finds all the indexes of a substring in a given string.

JavaScript, String · Dec 31, 2020

• ### Escape HTML

Escapes a string for use in HTML.

JavaScript, String · Oct 13, 2021