```
class Solution(object):
def minDistance(self, word1, word2):
if not word1 and not word2: return 0
dp = [[-1 for j in xrange(len(word2)+1)] for i in xrange(len(word1)+1)]
for i in xrange(len(word1)+1):
for j in xrange(len(word2)+1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
return dp[len(word1)][len(word2)]
```