40 lines
857 B
Text
40 lines
857 B
Text
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")
|