def editDistance(a, b)
  case
    when a.empty?: b.length
    when b.empty?: a.length
    else [(a[0] == b[0] ? 0 : 1) + editDistance(a[1..-1], b[1..-1]),
          1 + editDistance(a[1..-1], b),
          1 + editDistance(a, b[1..-1])].min
  end
end

def editDistance(a, b): 
   if not a: return len(b)
   if not b: return len(a)
   return min([int(a[0] != b[0]) + editDistance(a[1:], b[1:]), 
              1 + editDistance(a[1:], b), 
              1 + editDistance(a, b[1:])])

def distance(a,b):
    "Calculates the Levenshtein distance between a and b."
    n, m = len(a), len(b)
    if n > m:
        # Make sure n <= m, to use O(min(n,m)) space
        a,b = b,a
        n,m = m,n
    current = range(n+1)
    for i in range(1,m+1):
        previous, current = current, [i]+[0]*n
        for j in range(1,n+1):
            add, delete = previous[j]+1, current[j-1]+1
            change = previous[j-1]
            if a[j-1] != b[i-1]:
                change = change + 1
            current[j] = min(add, delete, change)
    return current[n]