## Description

Given a string *s1*, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of *s1* = `"great"`

:

```
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t
```

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node `"gr"`

and swap its two children, it produces a scrambled string `"rgeat"`

.

```
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t
```

We say that `"rgeat"`

is a scrambled string of `"great"`

.

Similarly, if we continue to swap the children of nodes `"eat"`

and `"at"`

, it produces a scrambled string `"rgtae"`

.

```
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a
```

We say that `"rgtae"`

is a scrambled string of `"great"`

.

Given two strings *s1* and *s2* of the same length, determine if *s2* is a scrambled string of *s1*.

**Example 1:**

```
Input: s1 = "great", s2 = "rgeat"
Output: true
```

**Example 2:**

```
Input: s1 = "abcde", s2 = "caebd"
Output: false
```

## Solutions

### 1. Recursion

s1 分成两个子串 s11 和 s12，s2 分成两个子串 s21 和 s22，如果是 Scramble string，那么要不是 (s11, s21)和 (s12, s22) 两组对应互为 scramble string，就是 (s11, s22) 和 (s12, s21) 两组互为子串。

```
# Time: O(n^2)
# Space: O(n)
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
n1, n2 = len(s1), len(s2)
if n1 != n2:
return False
if s1 == s2:
return True
str1 = sorted(s1)
str2 = sorted(s2)
# print(str1, str2)
if str1 != str2:
return False
for i in range(1, n1):
s11 = s1[:i]
s12 = s1[i:]
s21 = s2[:i]
s22 = s2[i:]
if self.isScramble(s11, s21) and self.isScramble(s12, s22):
return True
s21 = s2[-i:]
s22 = s2[:-i]
if self.isScramble(s11, s21) and self.isScramble(s12, s22):
return True
return False
# 283/283 cases passed (32 ms)
# Your runtime beats 98.75 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.6 MB)
```

### 2. 3D-DP

```
# Time: O(n^3)
# Space: O(n^3)
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
n1, n2 = len(s1), len(s2)
if n1 != n2:
return False
# /**
# * Let F(i, j, k) = whether the substring S1[i..i + k - 1] is a scramble of S2[j..j + k - 1] or not
# * Since each of these substrings is a potential node in the tree, we need to check for all possible cuts.
# * Let q be the length of a cut (hence, q < k), then we are in the following situation:
# *
# * S1 [ x1 | x2 ]
# * i i + q i + k - 1
# *
# * here we have two possibilities:
# *
# * S2 [ y1 | y2 ]
# * j j + q j + k - 1
# *
# * or
# *
# * S2 [ y1 | y2 ]
# * j j + k - q j + k - 1
# *
# * which in terms of F means:
# *
# * F(i, j, k) = for some 1 <= q < k we have:
# * (F(i, j, q) AND F(i + q, j + q, k - q)) OR (F(i, j + k - q, q) AND F(i + q, j, k - q))
# *
# * Base case is k = 1, where we simply need to check for S1[i] and S2[j] to be equal
# * */
dp = [[[False for _ in range(n1+1)] for _ in range(n1)]for _ in range(n1)]
for k in range(1, n1 + 1):
i = 0
while i + k <= n1:
j = 0
while j + k <= n1:
if k == 1:
dp[i][j][k] = s1[i] == s2[j]
else:
q = 1
while q < k and not dp[i][j][k]:
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])
q += 1
j += 1
i += 1
return dp[0][0][n1]
# 283/283 cases passed (548 ms)
# Your runtime beats 5.14 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.8 MB)
```