string.editDistance = function(s2)
  n = self.len
  m = s2.len
  if n == 0 then return m
  if m == 0 then return n

  s1chars = self.split("")
  s2chars = s2.split("")
  d = range(0, m)
  lastCost = 0

  for i in range(1, n)
    s1char = s1chars[i-1]
    lastCost = i
    jMinus1 = 0
    for j in range(1, m)
      if s1char == s2chars[jMinus1] then cost = 0 else cost = 1

      // set nextCost to the minimum of the following three possibilities:
      a = d[j] + 1
      b = lastCost + 1
      c = cost + d[jMinus1]

      if a < b then
        if c < a then nextCost = c else nextCost = a
      else
        if c < b then nextCost = c else nextCost = b
      end if

      d[jMinus1] = lastCost
      lastCost = nextCost
      jMinus1 = j
    end for
    d[m] = lastCost
  end for

  return nextCost
end function

print "kitten".editDistance("sitting")