Python O(m*n) Time O(n) space DP


  • 0
    E

    Classic DP Problem. We can optimize space utilization by using a rolling array for a row at a time and using values form the array directly as they represent values from the previous row before update.

        def minDistance(self, word1, word2):
            """
            :type word1: str
            :type word2: str
            :rtype: int
            """
            if not word1 or not word2: 
                return len(word1) if not word2 else len(word2)
            w1, w2 = len(word1)+1, len(word2)+1
            row = range(w1)
            for i in range(1, w2):
                prev, row[0] = row[0], i
                for j in range(1, w1):
                    prev, row[j] = row[j], min(prev+(word1[j-1]!=word2[i-1]), row[j-1]+1, row[j]+1)
            return row[-1]
    

Log in to reply
 

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