# Share a Python solution with memorization 220 ms

• ``````class Solution(object):
def isScramble(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
dp = {}
def dfs(s1, s2):
if s1 > s2:
return dfs(s2, s1)
if (s1, s2) not in dp:
dp[(s1, s2)] = s1 == s2
if not dp[(s1, s2)] and sorted(s1) == sorted(s2):
for i in range(1, len(s1)):
if (dfs(s1[:i], s2[:i]) and dfs(s1[i:], s2[i:])) or\
(dfs(s1[:i], s2[-i:]) and dfs(s1[i:], s2[:-i])):
dp[(s1, s2)] = True
return dp[(s1, s2)]
return dfs(s1, s2)
``````

The "normal" dp solution is slower than this one.

• ``````class Solution(object):
def isScramble(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
if sorted(s1) != sorted(s2):
return False
# check scramble
n = len(s1)
# whether s2[j:j + k] is a scramble of s1[i:i + k]
dp = [[[False for j in range(n)] for i in range(n)] for k in range(n + 1)]
for i in range(n):
for j in range(n):
if s1[i] == s2[j]:
dp[1][i][j] = True
for k in range(2, n + 1):
for i in range(n + 1 - k):
for j in range(n + 1 - k):
# each split might form scramble
for p in range(1, k):
# no swap or swap is scramble
if (dp[p][i][j] and dp[k - p][i + p][j + p])\
or (dp[p][i][j + k - p] and dp[k - p][i + p][j]):
dp[k][i][j] = True
break
return dp[n][0][0]
``````

460ms

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