<p>《远处的忍者数学》的简短解释:</p>
<pre><code> # this is just the edit distance (Levenshtein) between the two words
def distance(self, s1, s2):
l1 = len(s1) # length of first word
l2 = len(s2) # length of second word
matrix = [range(zz,zz + l1 + 1) for zz in xrange(l2 + 1)]
# make an l2 + 1 by l1 + 1 matrix where the first row and column count up from
# 0 to l1 and l2 respectively (these will be the costs of
# deleting the letters that came before that element in each word)
for zz in xrange(0,l2):
for sz in xrange(0,l1):
if s1[sz] == s2[zz]: # if the two letters are the same then we
# don't have to change them so take the
# cheapest path from the options of
# matrix[zz+1][sz] + 1 (delete the letter in s1)
# matrix[zz][sz+1] + 1 (delete the letter in s2)
# matrix[zz][sz] (leave both letters)
matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz])
else: # if the two letters are not the same then we
# have to change them so take the
# cheapest path from the options of
# matrix[zz+1][sz] + 1 (delete the letter in s1)
# matrix[zz][sz+1] + 1 (delete the letter in s2)
# matrix[zz][sz] + 1 (swap a letter)
matrix[zz+1][sz+1] = min(matrix[zz+1][sz] + 1, matrix[zz][sz+1] + 1, matrix[zz][sz] + 1)
return matrix[l2][l1] # the value at the bottom of the matrix is equal to the cheapest set of edits
</code></pre>