utils.ts•687 B
export function levenshteinDistance(a: string, b: string): number {
const matrix: number[][] = Array(b.length + 1).fill(null).map(() => Array(a.length + 1).fill(null));
for (let i = 0; i <= a.length; i += 1) {
matrix[0][i] = i;
}
for (let j = 0; j <= b.length; j += 1) {
matrix[j][0] = j;
}
for (let j = 1; j <= b.length; j += 1) {
for (let i = 1; i <= a.length; i += 1) {
const indicator = a[i - 1] === b[j - 1] ? 0 : 1;
matrix[j][i] = Math.min(
matrix[j][i - 1] + 1, // deletion
matrix[j - 1][i] + 1, // insertion
matrix[j - 1][i - 1] + indicator, // substitution
);
}
}
return matrix[b.length][a.length];
}