Skip to content

Instantly share code, notes, and snippets.

@olistik

olistik/gist:73a379efadd64d96b5eb Secret

Created April 25, 2015 10:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save olistik/73a379efadd64d96b5eb to your computer and use it in GitHub Desktop.
Save olistik/73a379efadd64d96b5eb to your computer and use it in GitHub Desktop.
Download ZIP
Raw
gistfile1.rb
ಠ_ಠ cat levenshtein_distance.rb
def levenshtein_distance(str1, str2)
n = str1.length
m = str2.length
max = n/2
return m if 0 == n
return n if 0 == m
return n if (n - m).abs > max
d = (0..m).to_a
x = nil
str1.each_char.with_index do |char1,i|
e=i+1
str2.each_char.with_index do |char2,j|
cost=(char1==char2) ? 0 : 1
x=[d[j+1]+1, e+1, d[j]+cost].min
d[j]=e
e=x
end
d[m]=x
end
x
end
puts levenshtein_distance 'foo', 'spam'
ಠ_ಠ ruby levenshtein_distance.rb
4
ಠ_ಠ ruby -v
ruby 2.2.0p0 (2014-12-25 revision 49005) [x86_64-darwin14]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment