32 lines
850 B
JavaScript
32 lines
850 B
JavaScript
function levenshtein(a, b) {
|
|
var t = [], u, i, j, m = a.length, n = b.length;
|
|
if (!m) { return n; }
|
|
if (!n) { return m; }
|
|
for (j = 0; j <= n; j++) { t[j] = j; }
|
|
for (i = 1; i <= m; i++) {
|
|
for (u = [i], j = 1; j <= n; j++) {
|
|
u[j] = a[i - 1] === b[j - 1] ? t[j - 1] : Math.min(t[j - 1], t[j], u[j - 1]) + 1;
|
|
} t = u;
|
|
} return u[n];
|
|
}
|
|
|
|
// tests
|
|
[ ['', '', 0],
|
|
['yo', '', 2],
|
|
['', 'yo', 2],
|
|
['yo', 'yo', 0],
|
|
['tier', 'tor', 2],
|
|
['saturday', 'sunday', 3],
|
|
['mist', 'dist', 1],
|
|
['tier', 'tor', 2],
|
|
['kitten', 'sitting', 3],
|
|
['stop', 'tops', 2],
|
|
['rosettacode', 'raisethysword', 8],
|
|
['mississippi', 'swiss miss', 8]
|
|
].forEach(function(v) {
|
|
var a = v[0], b = v[1], t = v[2], d = levenshtein(a, b);
|
|
if (d !== t) {
|
|
console.log('levenstein("' + a + '","' + b + '") was ' + d + ' should be ' + t);
|
|
}
|
|
});
|