```
class Solution:
# @param {string} word1
# @param {string} word2
# @return {integer}
def minDistance(self, word1, word2): #AC 311ms
"""
2D version
"""
n, m = len(word1), len(word2)
if n*m == 0:
return n or m
dp = [ [0 for _ in range(n+1)] for _ in range(m+1)]
for j in range(m+1):
dp[j][0] = j
for i in range(n+1):
dp[0][i] = i
word1 = ' '+ word1 # padding for clearer index
word2 = ' '+ word2
for j in range(1, m+1):
for i in range(1, n+1):
cost = 1 if word1[i] != word2[j] else 0
dp[j][i] = min( dp[j-1][i-1]+cost, dp[j][i-1]+1, dp[j-1][i]+1)
return dp[-1][-1]
def minDistance(self, word1, word2): # AC 236ms
"""
1D version, space: O(n), forget +1 for insert and delete.
"""
n, m = len(word1), len(word2)
if n*m == 0:
return n or m
word1 = ' '+ word1
word2 = ' '+ word2
prev = range(n+1)
for j in range(1, m+1):
current = [j] + [0]*n
for i in range(1, n+1):
possible_cost = 1 if word1[i] != word2[j] else 0
current[i] = min(prev[i-1] + possible_cost, prev[i] + 1, current[i-1] + 1)
# prev[i-1] + possible_cost -> match/replace
# prev[i]] -> insert after i, so i match j-1
# current[i-1] -> delete i, so i-1 match j
prev = current
return prev[-1]
```