owsei revised this gist . Go to revision
1 file changed, 17 insertions
levenshtein.js(file created)
| @@ -0,0 +1,17 @@ | |||
| 1 | + | function lev(a, b) { | |
| 2 | + | if (!a.length) return b.length; | |
| 3 | + | if (!b.length) return a.length; | |
| 4 | + | const arr = []; | |
| 5 | + | for (let i = 0; i <= b.length; i++) { | |
| 6 | + | arr[i] = [i]; | |
| 7 | + | for (let j = 1; j <= a.length; j++) { | |
| 8 | + | arr[i][j] = i === 0 ? | |
| 9 | + | j : Math.min( | |
| 10 | + | arr[i - 1][j] + 1, | |
| 11 | + | arr[i][j - 1] + 1, | |
| 12 | + | arr[i - 1][j - 1] + (a[j - 1] === b[i - 1] ? 0 : 1) | |
| 13 | + | ); | |
| 14 | + | } | |
| 15 | + | } | |
| 16 | + | return arr[b.length][a.length]; | |
| 17 | + | }; | |
Newer
Older