# Levenshtein distance (v17)

## Setup

``````function levenshtein_distance_a (a, b) {
if(a.length == 0) return b.length;
if(b.length == 0) return a.length;

var matrix = [];

// increment along the first column of each row
var i;
for(i = 0; i <= b.length; i++){
matrix[i] = [i];
}

// increment each column in the first row
var j;
for(j = 0; j <= a.length; j++){
matrix[0][j] = j;
}

// Fill in the rest of the matrix
for(i = 1; i <= b.length; i++){
for(j = 1; j <= a.length; 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] + 1, // substitution
Math.min(matrix[i][j-1] + 1, // insertion
matrix[i-1][j] + 1)); // deletion
}
}
}

return matrix[b.length][a.length];
}

function levenshtein_distance_b (s, t) {
var d = []; //2d matrix

// Step 1
var n = s.length;
var m = t.length;

if (n == 0) return m;
if (m == 0) return n;

//Create an array of arrays in javascript (a descending loop is quicker)
for (var i = n; i >= 0; i--) d[i] = [];

// Step 2
for (var i = n; i >= 0; i--) d[i][0] = i;
for (var j = m; j >= 0; j--) d[0][j] = j;

// Step 3
for (var i = 1; i <= n; i++) {
var s_i = s.charAt(i - 1);

// Step 4
for (var j = 1; j <= m; j++) {

//Check the jagged ld total so far
if (i == j && d[i][j] > 4) return n;

var t_j = t.charAt(j - 1);
var cost = (s_i == t_j) ? 0 : 1; // Step 5

//Calculate the minimum
var mi = d[i - 1][j] + 1;
var b = d[i][j - 1] + 1;
var c = d[i - 1][j - 1] + cost;

if (b < mi) mi = b;
if (c < mi) mi = c;

d[i][j] = mi; // Step 6

//Damerau transposition
if (i > 1 && j > 1 && s_i == t.charAt(j - 2) && s.charAt(i - 2) == t_j) {
d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
}
}
}

// Step 7
return d[n][m];
}``````

## Test runner

``levenshtein_distance_a('frankenstein', 'frankestein')``
``levenshtein_distance_b('frankenstein', 'frankestein')``