defedit_distance(a, b): la = len(a) lb = len(b) dp = [[0for i in xrange(lb + 1)] for j in xrange(la + 1)] for i in xrange(1, la + 1): dp[i][0] = i for j in xrange(1, lb + 1): dp[0][j] = j for i in xrange(la): for j in xrange(lb): if a[i] == b[j]: dp[i + 1][j + 1] = dp[i][j] else: dp[i + 1][j + 1] = min(dp[i + 1][j], dp[i][j + 1], dp[i][j]) + 1 return dp[la][lb]