```
class Solution(object):
#dp O(m*n) space
def minDistance1(self, word1, word2):
"""
:type word1: str
:type word2: str
:rtype: int
"""
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range (m+1) ]
for i in range (1, m+1):
dp[i][0] = i
for j in range (1, n+1):
dp[0][j] = j
for i in range (1, m+1):
for j in range (1, n+1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
return dp[-1][-1]
#dp O(2*n)space
def minDistance2(self, word1, word2):
m, n = len(word1), len(word2)
dp = [0]+[ i for i in range (1,n+1)]
for i in range (1, m+1):
prev = dp[:]
dp[0] = dp[0]+1
for j in range (1, n+1):
if word1[i-1] == word2[j-1]:
dp[j] = prev[j-1]
else:
dp[j] = min(dp[j], dp[j-1], prev[j-1])+1
return dp[-1]
#recursive O(m*n)space
def minDistance(self, word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n+1) for _ in range (m+1)]
def helper(i, j):
if not dp[i][j]:
if i==0:
dp[i][j] = j
elif j==0:
dp[i][j] = i
elif word1[i-1] == word2[j-1]:
dp[i][j] = helper(i-1, j-1)
else:
dp[i][j] = min(helper(i-1,j), helper(i,j-1), helper(i-1,j-1))+1
return dp[i][j]
return helper(m, n)
```