Need Helps for Optimzation if using backtrack


  • 0
    D

    Hi, I am trying to figure out the problem using backtrack technique, is it even possible to do so?

    How should I improve the code to make it work without TLE by memorization? or some optimization regarding to the constraints in this problem?

    Thanks in advance!

    class Solution(object):
        def minimumDeleteSum(self, s1, s2):
            """
            :type s1: str
            :type s2: str
            :rtype: int
            """
            n1 = len(s1)
            n2 = len(s2)
            nmax = max(n1,n2)
            self.best = ord('z')*nmax
            
            t1limit = (1<<len(s1))-1
            t2limit = (1<<len(s2))-1
            
            def bt(si,sj,taken1,taken2,cursum):
                if taken1 == t1limit:
                    return
                if taken2 == t2limit:
                    return 
                if si == sj:
                    if self.best > cursum:
                        self.best = cursum
                    return
                for i,c in enumerate(si):
                    if (taken1>>i) & 1 == 0:
                        if self.best < (cursum + ord(c)):
                            break
                        bt(si[0:i]+si[i+1:], sj,taken1 + (1<<i), taken2, cursum + ord(c))
                for i,c in enumerate(sj):
                    if (taken2>>i) & 1 == 0:
                        if self.best < (cursum + ord(c)):
                            break
                        bt(si, sj[0:i]+sj[i+1:],taken1, taken2+ (1<<i), cursum + ord(c))        
            bt(s1,s2,0,0,0)
            return self.best
    

Log in to reply
 

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