benjohn
8/1/2006 1:20:00 PM
>>It's missing from wikipedia though.
>
> Does wikipedia provide the code for the implementations it lists?
> Maybe Hal would be so kind to add it then, if we ask him politely
> to do so :)
>
> Best regards,
Here's my implementation anyway (not at all fast):
def lev(s1, s2)
# A hash to build up the solution matrix in.
l = Hash.new do |h,k|
h = if k.member? 0
# Edge case for the top and left of the solution matrix.
k.max
else
# Otherwise, recursively find this cell based on the rest of
# the solution matrix.
i,j = *k
[ l[[i-1,j]]+1,
l[[i,j-1]]+1,
l[[i-1,j-1]] + (s1[i]==s2[j]?0:1)].min
end
end
# The answer's stored in the bottom right of the solution matrix.
l[[s1.size-1, s2.size-1]]
end