Python DP O(n) space


  • 0
    L
    class Solution(object):
        def minDistance(self, word1, word2):
            """
            :type word1: str
            :type word2: str
            :rtype: int
            """
            l1,l2=len(word1)+1,len(word2)+1
            dp=range(l2)
            for i in range(1,l1):
                curr=[i]*l2
                for j in range(1,l2):
                    if word1[i-1]==word2[j-1]:
                        curr[j]=dp[j-1]
                    else:
                        curr[j]=min(dp[j-1]+1,dp[j],curr[j-1])+1
                dp=curr
            return dp[-1] if l1 and l2 else abs(l1-l2)

Log in to reply
 

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