Skip to content

Instantly share code, notes, and snippets.

@asdrubalivan
Created June 7, 2014 16:38
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save asdrubalivan/a48b0a2cfbe3a9eb80fc to your computer and use it in GitHub Desktop.
Levenshtein distance algorithm in CoffeeScript
###
# @desc: Recursive Implementation of Levenshtein distance algorithm
# according to Wikipedia's pseudocode implementation of it
# @author: Asdrúbal Suárez (Twitter @asdrubalivan)
###
levenshteinInternal = (s, len_s, t, len_t) ->
if len_s is 0
return len_t
if len_t is 0
return len_s
cost = if s[len_s - 1] is t[len_t - 1] then 0 else 1
l1 = levenshteinInternal(s, len_s - 1, t, len_t) + 1
l2 = levenshteinInternal(s, len_s, t, len_t - 1) + 1
l3 = levenshteinInternal(s, len_s - 1, t, len_t - 1) + cost
Math.min l1, l2, l3
levenshtein = (s, t) ->
levenshteinInternal s, s.length, t, t.length
console.log levenshtein("book", "back")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment