Python DP Solution that won't accept TLE


  • 0
    B
    def minimumDeleteSum(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: int
        """
        l1 = len(s1)
        l2 = len(s2)
        mtx = [  [0 for cols in range(l1+1)] for rows in range(l2+1) ]
        
        for col in range(1,l1+1):
            mtx[0][col] = mtx[0][col-1] + ord(s1[col-1])
        for row in range(1,l2+1):
            mtx[row][0] = mtx[row-1][0] + ord(s2[row-1])
        for col in range(1,l1+1):
            for row in range(1,l2+1):
                if s1[col-1] == s2[row-1]:
                    mtx[row][col] = mtx[row-1][col-1]
                else:
                    mtx[row][col] = min(mtx[row-1][col]+ord(s2[row-1]),mtx[row][col-1]+ord(s1[col-1]))
        
        return mtx[-1][-1]
    

    EDIT: not sure why but now it's accepting, it was throwing Time limit exceeded exception on the last test case, but now it accepted for the exact code,


  • 0
    W

    It is too bad .I wonder whether there exists a python method.If no,this problem should not allow to be solved by python.


  • 0

    What does "won't accept TLE" mean? Does it throw a tantrum and scream "DON'T INTERRUPT ME!!!"? :-)

    @weidiao What about the Python solution that had already been posted long before you commented?


  • 0
    B

    I suck in the same problem. The complexity is O(n^2). I do not think it is too high


Log in to reply
 

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