Just to give a different view from DP. Quite efficient for this problem (139 ms beating 98%).

```
class Solution(object):
def minDistance(self, w1, w2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
m,n,d = len(w1),len(w2),{}
def mds(w1, w2, i, j):
if i*j==0: return i+j
if (i,j) in d: return d[(i,j)]
val = 0
if w1[i-1]==w2[j-1]:
val = mds(w1, w2, i-1, j-1)
else:
val = 1+min(mds(w1,w2,i,j-1),mds(w1,w2,i-1,j-1),mds(w1,w2,i-1,j))
d[(i,j)]=val
return val
return mds(w1,w2,m,n)
```