edit_distance.rb

def edit_distance(a, b)
  return 0 if !a || !b || a == b
  return (a.length - b.length).abs if a.length == 0 || b.length == 0
  m = [[0]]
  1.upto(a.length) { |i| m[i] = [i] }
  1.upto(b.length) { |j| m[0][j] = j }
  1.upto(a.length) do |i|
    1.upto(b.length) do |j|
      m[i][j] =
      [ m[i-1][j-1] + (a[i-1] == b[j-1] ? 0 : 1),
      m[i-1][j] + 1,
      m[i][j-1] + 1].min
    end
  end
  m[a.length][b.length]
end