Accepted O(mn) Python Solution


  • 0
    H

    Concise solution. Any suggestions will be appreciated.

    class Solution(object):
        def minDistance(self, word1, word2):
            """
            :type word1: str
            :type word2: str
            :rtype: int
            """
            if not len(word1) or not len(word2):
                return len(word1)+len(word2)
            if len(word1) < len(word2):
                word1, word2 = word2, word1
            l1, l2 = len(word1), len(word2)
            dp= [0]*(l1+1)
            pre = [l2-j for j in xrange(l1+1)]
            for i in xrange(l1-1, -1, -1):
                for j in xrange(l1, l2-1,-1):
                    dp[j] = l1-i
                for j in xrange(l2-1, -1, -1):
                    dp[j] = min(pre[j+1] + [1,0][word1[i]==word2[j]],1+min(dp[j+1], pre[j]))
                dp, pre = [0]*(l1+1), dp
            return pre[0]
    

Log in to reply
 

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