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


  • 1
    I
    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]

Log in to reply
 

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