# Need Helps for Optimzation if using backtrack

• 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?

``````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
``````

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