I use DP but i got TLE.


  • 0
    W
    class Solution:
    # @return an integer
    def minDistance(self, word1, word2):
        maxNum = max(len(word1), len(word2))
        if len(word1) == 0 or len(word2) == 0:
            return maxNum
    
        lcsNum = self.lcs(word1, word2)
        return maxNum - lcsNum
        
    def lcs(self, str1, str2):
        if len(str1) == 0 or len(str2) == 0:
            return 0
        matrix =[[0 for i in range(len(str1) + 1)] for j in range((len(str2) + 1))]
        print matrix
        for i in range(1, len(str2) + 1):
            for j in range(1, len(str1) + 1):
                if str1[j-1] == str2[i-1]:
                    matrix[i][j] = max(matrix[i-1][j-1] + 1, matrix[i-1][j])
                else:
                    matrix[i][j] = max(matrix[i][j-1], matrix[i-1][j])
        return matrix[i][j]
    

    but i got TLE all the time with my code, i use DP so should be ok. no idea why.


  • 1
    S

    The code looks okay, but why do you want to print the matrix?


Log in to reply
 

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