Levenshtein Distance

by soulwire

JavaScript

var words = ['the cat', 'there', 'cat', 'thorn', 'other'];
var term = 'them cats';

function levenshtein(a, b) {
    var x = a.length, y = b.length;
    var i, j, d = [];
    for(i = 0; i <= x; i++) {
        d[i] = [];
        d[i][0] = i;
    }
    for(i = 0; i <= y; i++) {
        d[0][i] = i;
    }
    for(i = 1; i <= x; i++) {
      for(j = 1; j <= y; j++) {
          d[i][j] = Math.min(
              d[i - 1][j] + 1,
              d[i][j - 1] + 1, 
              d[i - 1][j - 1] + (a.charAt(i - 1) === b.charAt(j - 1) ? 0 : 1)
          );
      }  
    }
    return d[x][y];
}

for(var i = 0, n = words.length; i < n; i++) {
    console.log( term ,words[i], levenshtein(term, words[i]) );
}