def edit_distance(s1, s2):
d = {}<EOL>lenstr1 = len(s1)<EOL>lenstr2 = len(s2)<EOL>for i in xrange(-<NUM_LIT:1>, lenstr1 + <NUM_LIT:1>):<EOL><INDENT>d[(i, -<NUM_LIT:1>)] = i + <NUM_LIT:1><EOL><DEDENT>for j in xrange(-<NUM_LIT:1>, lenstr2 + <NUM_LIT:1>):<EOL><INDENT>d[(-<NUM_LIT:1>, j)] = j + <NUM_LIT:1><EOL><DEDENT>for i in xrange(lenstr1):<EOL><INDENT>for j in xrange(lenstr2):<EOL><INDENT>if s1[i] == s2[j]:<EOL><INDENT>cost = <NUM_LIT:0><EOL><DEDENT>else:<EOL><INDENT>cost = <NUM_LIT:1><EOL><DEDENT>d[(i, j)] = min(<EOL>d[(i - <NUM_LIT:1>, j)] + <NUM_LIT:1>, <EOL>d[(i, j - <NUM_LIT:1>)] + <NUM_LIT:1>, <EOL>d[(i - <NUM_LIT:1>, j - <NUM_LIT:1>)] + cost, <EOL>)<EOL>if i and j and s1[i] == s2[j - <NUM_LIT:1>] and s1[i - <NUM_LIT:1>] == s2[j]:<EOL><INDENT>d[(i, j)] = min(d[(i, j)], d[i - <NUM_LIT:2>, j - <NUM_LIT:2>] + cost) <EOL><DEDENT><DEDENT><DEDENT>return d[lenstr1 - <NUM_LIT:1>, lenstr2 - <NUM_LIT:1>]<EOL>
Calculates string edit distance between string 1 and string 2.
Deletion, insertion, substitution, and transposition all increase edit distance.