Skip to content

Instantly share code, notes, and snippets.

@keesey
Last active February 14, 2024 10:59
Show Gist options
  • Star 6 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save keesey/e09d0af833476385b9ee13b6d26a2b84 to your computer and use it in GitHub Desktop.
Save keesey/e09d0af833476385b9ee13b6d26a2b84 to your computer and use it in GitHub Desktop.
Levenshtein distance implemented in TypeScript
export function levenshtein(a: string, b: string): number
{
const an = a ? a.length : 0;
const bn = b ? b.length : 0;
if (an === 0)
{
return bn;
}
if (bn === 0)
{
return an;
}
const matrix = new Array<number[]>(bn + 1);
for (let i = 0; i <= bn; ++i)
{
let row = matrix[i] = new Array<number>(an + 1);
row[0] = i;
}
const firstRow = matrix[0];
for (let j = 1; j <= an; ++j)
{
firstRow[j] = j;
}
for (let i = 1; i <= bn; ++i)
{
for (let j = 1; j <= an; ++j)
{
if (b.charAt(i - 1) === a.charAt(j - 1))
{
matrix[i][j] = matrix[i - 1][j - 1];
}
else
{
matrix[i][j] = Math.min(
matrix[i - 1][j - 1], // substitution
matrix[i][j - 1], // insertion
matrix[i - 1][j] // deletion
) + 1;
}
}
}
return matrix[bn][an];
};
@hsoulier
Copy link

hsoulier commented Feb 14, 2024

Very simple and practical implementation of the Levenshtein algorithm ! Thanks

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment