# Iterative(dp) and recursive in python

• ``````class Solution(object):
def isScramble1(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
if len(s1)!=len(s2): return False
length = len(s1)
dp = [[[False]*(length+1) for i in range (length)] for j in range (length)]
for k in range (1, length+1):
for i in range(0, length+1-k):
for j in range(0, length+1-k):
if k ==1:
dp[i][j][k] = s1[i]==s2[j]
else:
for q in range(1, k):
if dp[i][j][k]: break
else:
dp[i][j][k] = dp[i][j][q] and dp[i+q][j+q][k-q] or dp[i][j+k-q][q] and dp[i+q][j][k-q]
return dp[0][0][length]

def isScramble(self, s1, s2):
dp = {}

def helper(s1, s2):
if (s1, s2) in dp:
return dp[(s1, s2)]
if len(s1)==1:
return s1==s2
if len(s1) != len(s2) or sorted(s1)!= sorted(s2):
return False
for i in range (1,len(s1)):
if helper(s1[:i], s2[:i]) and helper(s1[i:] , s2[i:]) or helper(s1[:i], s2[-i:]) and helper(s1[i:], s2[:-i]):
dp[(s1,s2)] = True
return True
dp[(s1,s2)] = False
return False

return helper(s1, s2)``````

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