Skip to content

Instantly share code, notes, and snippets.

@hyamamoto
Created June 22, 2016 08:14
Show Gist options
  • Save hyamamoto/09dfcef180637bdf921963e183f27a54 to your computer and use it in GitHub Desktop.
Save hyamamoto/09dfcef180637bdf921963e183f27a54 to your computer and use it in GitHub Desktop.
The string.levenstein() function will get you an edit distance between 2 string values.
if (!String.prototype.levenstein) {
String.prototype.levenstein = (function(string) {
// source originated from https://gist.github.com/andrei-m/982927#gistcomment-1797205
var a = this, b = string + "", m = [], i, j, min = Math.min;
if (!(a && b)) return (b || a).length;
for (i = 0; i <= b.length; m[i] = [i++]);
for (j = 0; j <= a.length; m[0][j] = j++);
for (i = 1; i <= b.length; i++) {
for (j = 1; j <= a.length; j++) {
m[i][j] = b.charAt(i - 1) == a.charAt(j - 1) ?
m[i - 1][j - 1] :
m[i][j] = min(
m[i - 1][j - 1] + 1,
min(m[i][j - 1] + 1, m[i - 1 ][j] + 1));
}
}
return m[b.length][a.length];
});
}
>> "Hello".levenstein("Hello")
0
>> "Hello".levenstein("Hell")
1
>> "Hello".levenstein("Willow")
3
>> "Hello".levenstein("World")
4
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment