# Python code for 1D and 2D implementation, with minor comments

• ``````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]``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.