```
def minDistance(self, word1, word2):
m, n = len(word1), len(word2)
r = [[0 for _ in xrange(n+1)] for _ in xrange(m+1)]
for i in xrange(m, -1, -1):
for j in xrange(n, -1, -1):
if i == m or j == n:
r[i][j] = max(m-i, n-j)
elif word1[i] == word2[j]:
r[i][j] = r[i+1][j+1]
else:
r[i][j] = 1 + min(r[i+1][j], r[i][j+1], r[i+1][j+1])
return r[0][0]
```