python DP O(n) solution


  • 0
    A
    class Solution(object):
        def minDistance(self, word1, word2):
            """
            :type word1: str
            :type word2: str
            :rtype: int
            """
            dp = [0] * (len(word2) + 1)
            for c1 in word1:
                newdp = dp[:]
                for i, c2 in enumerate(word2):
                    if c1 == c2:
                        newdp[i+1] = 1 + dp[i]
                    else:
                        newdp[i+1] = max(dp[i+1], newdp[i])
                dp = newdp
            return len(word1) + len(word2) - dp[-1] * 2

Log in to reply
 

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