A/C Python, DP, easy to understand, beat 47%


  • 0
    W
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        len1 = len(word1)
        len2 = len(word2)
    
        #print "len1 = ", len1, " len2 =", len2
    
        if len1 ==0 or len2 == 0:
            return len1+len2
    
        matrix = [[0 for i in range(len1+1)] for j in range(len2+1)]
        #print "1 matrix = ", matrix
    
        sameSubListLen = 0
        for idx2 in range(1,len2+1):
            for idx1 in range(1,len1+1):
                #print "compare ", word2[idx2], " and ", word1[idx1]
    
                if word2[idx2-1] == word1[idx1-1]:
                    #print "they are the same", " idx2 = ", idx2, "  idx1 = ", idx1
                    matrix[idx2][idx1] = matrix[idx2-1][idx1-1] + 1
                    # else:
                    #     matrix[idx2][idx1] = 1
                else:
                    matrix[idx2][idx1] = max(matrix[idx2][idx1-1], matrix[idx2-1][idx1])
    
                if matrix[idx2][idx1] > sameSubListLen:
                    sameSubListLen = matrix[idx2][idx1]
    
    
        #print "2 matrix = ", matrix
    
        #print "sameSubListLen = ", sameSubListLen
    
        res = len1 - sameSubListLen + (len2 - sameSubListLen)
        #print "res = ", res
    
        return res

Log in to reply
 

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