# Python dynamic programming solution TLE

• Here is my solution. Similar to other DP solutions but in Python.
OJ: Last executed input: "pcighfdjnbwfkohtklrecxnooxyipj", "npodkfchrfpxliocgtnykhxwjbojie"
I wrote a pure recursive Python solution and it is accepted but not DP solution.
Anyone knows why?

``````class Solution:
# @return a boolean
def isScramble(self, s1, s2):
if sorted(s1)!=sorted(s2):
return False
else:
n=len(s1)
dp=[[[s1[j]==s2[k] if i==0 else False for i in range(n)] for j in range(n)]for k in range(n)]
for L in range(2,n+1):
for i in range(n-L+1):
for j in range(n-L+1):
for m in range(1,L):
if dp[i][j][L-1]:
break
dp[i][j][L-1]=(dp[i][j][m-1] and dp[i+m][j+m][L-m-1]) or (dp[i+m][j][L-m-1] and dp[i][j+L-m][m-1])
return dp[0][0][n-1]``````

• Same thing happened to me. On my laptop the code runs for less than 0.1s.
Can you post your recursive solution?

``````class Solution:
# @return a boolean
def isScramble(self, s1, s2):
if not len(s1) == len(s2):
return False
N = len(s1)
dp = [ [ [ None for ___ in xrange(N+1) ] for __ in xrange(N+1) ] \
for _ in xrange(N+1)]
for i in xrange(0, N):
for j in xrange(0, N):
dp[i][j][1] = bool(s1[i] == s2[j])
# length of substring for examination
for l in xrange(1, N+1):
# loop through starting pos of s1
for i in xrange(0, N-l+1):
# loop through starting pos of s2
for j in xrange(0, N-l+1):
# position to cut
for p in xrange(1, l):
# left of s1 cut is-scramble left of s2 cut
# and right of s1 cut is-scramble right of s2 cut
a = dp[i][j][p] and dp[i+p][j+p][l-p]
# left of s1 cut is-scramble right of s2 cut
# and left of s1 cut is-scramble right of s2 cut
b = dp[i][j+l-p][p] and dp[i+p][j][l-p]
dp[i][j][l] = bool(a or b)
return dp[0][0][N]
``````

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