99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
|
-
-
+
+
|
nLen2 = len(s2)
for i in range(-1, nLen1+1):
d[i, -1] = i + 1
for j in range(-1, nLen2+1):
d[-1, j] = j + 1
for i in range(nLen1):
for j in range(nLen2):
#nCost = 0 if s1[i] == s2[j] else 1
nCost = distanceBetweenChars(s1[i], s2[j])
nCost = 0 if s1[i] == s2[j] else 1
#nCost = distanceBetweenChars(s1[i], s2[j])
d[i, j] = min(
d[i-1, j] + 1, # Deletion
d[i, j-1] + 1, # Insertion
d[i-1, j-1] + nCost, # Substitution
)
if i and j and s1[i] == s2[j-1] and s1[i-1] == s2[j]:
d[i, j] = min(d[i, j], d[i-2, j-2] + nCost) # Transposition
|