Home Communities
IT Knowledge
Inspiration
Languages
EN

# JavaScript - calculate Levenshtein distance between strings

20 points
Created by:
666

In this short article, we would like to show simple JavaScript implementation for the Levenstein distance algorithm.

Levenstein distance algorithm is used to measure the difference between two sequences (e.g. between two strings).

When the algorithm returns `0` it means: compared objects are equal.

Quick solution:

``````// ONLINE-RUNNER:browser;

const calculateLevenshteinDistance = (a, b) => {
const c = a.length + 1;
const d = b.length + 1;
const r = Array(c);
for (let i = 0; i < c; ++i) r[i] = Array(d);
for (let i = 0; i < c; ++i) r[i][0] = i;
for (let j = 0; j < d; ++j) r[0][j] = j;
for (let i = 1; i < c; ++i) {
for (let j = 1; j < d; ++j) {
const s = (a[i - 1] === b[j - 1] ? 0 : 1);
r[i][j] = Math.min(r[i - 1][j] + 1, r[i][j - 1] + 1, r[i - 1][j - 1] + s);
}
}
return r[a.length][b.length];
};

// Usage example:

console.log(calculateLevenshteinDistance('Chris',  'Chris'));  // 0
console.log(calculateLevenshteinDistance('John1',  'John2'));  // 1
console.log(calculateLevenshteinDistance('Google', 'Gogle'));  // 1
console.log(calculateLevenshteinDistance('Ann',    'Matt' ));  // 4

console.log(calculateLevenshteinDistance('CHRIS',  'Chris'));  // 4``````

## Alternative solution

In this section, you can find some solution that is at the beginning of this article but with more clear variable names.

``````// ONLINE-RUNNER:browser;

const calculateLevenshteinDistance = (a, b) => {
const aLimit = a.length + 1;
const bLimit = b.length + 1;
const distance = Array(aLimit);
for (let i = 0; i < aLimit; ++i) {
distance[i] = Array(bLimit);
}
for (let i = 0; i < aLimit; ++i) {
distance[i][0] = i;
}
for (let j = 0; j < bLimit; ++j) {
distance[0][j] = j;
}
for (let i = 1; i < aLimit; ++i) {
for (let j = 1; j <  bLimit; ++j) {
const substitutionCost = (a[i - 1] === b[j - 1] ? 0 : 1);
distance[i][j] = Math.min(
distance[i - 1][j] + 1,
distance[i][j - 1] + 1,
distance[i - 1][j - 1] + substitutionCost
);
}
}
return distance[a.length][b.length];
};

// Usage example:

console.log(calculateLevenshteinDistance('Chris',  'Chris'));  // 0
console.log(calculateLevenshteinDistance('John1',  'John2'));  // 1
console.log(calculateLevenshteinDistance('Google', 'Gogle'));  // 1
console.log(calculateLevenshteinDistance('Ann',    'Matt' ));  // 4

console.log(calculateLevenshteinDistance('CHRIS',  'Chris'));  // 4``````

## Levenstein distance algorithm with case-insensitive

It is necessary to wrap the existing algorithm with `toLowerCase()` or `toUpperCase()` string transformation.

``````// ONLINE-RUNNER:browser;

const calculateLevenshteinDistance = (a, b) => {
const aLimit = a.length + 1;
const bLimit = b.length + 1;
const distance = Array(aLimit);
for (let i = 0; i < aLimit; ++i) {
distance[i] = Array(bLimit);
}
for (let i = 0; i < aLimit; ++i) {
distance[i][0] = i;
}
for (let j = 0; j < bLimit; ++j) {
distance[0][j] = j;
}
for (let i = 1; i < aLimit; ++i) {
for (let j = 1; j <  bLimit; ++j) {
const substitutionCost = (a[i - 1] === b[j - 1] ? 0 : 1);
distance[i][j] = Math.min(
distance[i - 1][j] + 1,
distance[i][j - 1] + 1,
distance[i - 1][j - 1] + substitutionCost
);
}
}
return distance[a.length][b.length];
};

const calculateImprovedLevenshteinDistance = (a, b) => {
return calculateLevenshteinDistance (a.toLowerCase(), b.toLowerCase());
};

// Usage example:

console.log(calculateImprovedLevenshteinDistance('CHRIS',  'Chris'));  // 0
console.log(calculateImprovedLevenshteinDistance('JOHN1',  'John2'));  // 1
console.log(calculateImprovedLevenshteinDistance('GOOGLE', 'Gogle'));  // 1
console.log(calculateImprovedLevenshteinDistance('ANN',    'Matt' ));  // 3``````

## References

1. Levenshtein distance - Wikipedia
Join to our subscribers to be up to date with content, news and offers.