Dp( O(m*n) space, O(2*n)space) and recursive( O(m*n) space) python


  • 0
    S
    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)

Log in to reply
 

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