Skip to content

Instantly share code, notes, and snippets.

@documentcloud

documentcloud/gist:202293

Created October 5, 2009 17:32
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save documentcloud/202293 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save documentcloud/202293 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
gistfile1.rb
def levenshtein(a, b)
case
when a.empty?: b.length
when b.empty?: a.length
else [(a[0] == b[0] ? 0 : 1) + levenshtein(a[1..-1], b[1..-1]),
1 + levenshtein(a[1..-1], b),
1 + levenshtein(a, b[1..-1])].min
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment