<p>We can scramble a string s to get a string t using the following algorithm:</p>

<ol>
	<li>If the length of the string is 1, stop.</li>
	<li>If the length of the string is &gt; 1, do the following:
	<ul>
		<li>Split the string into two non-empty substrings at a random index, i.e., if the string is <code>s</code>, divide it to <code>x</code> and <code>y</code> where <code>s = x + y</code>.</li>
		<li><strong>Randomly</strong>&nbsp;decide to swap the two substrings or to keep them in the same order. i.e., after this step, <code>s</code> may become <code>s = x + y</code> or <code>s = y + x</code>.</li>
		<li>Apply step 1 recursively on each of the two substrings <code>x</code> and <code>y</code>.</li>
	</ul>
	</li>
</ol>

<p>Given two strings <code>s1</code> and <code>s2</code> of <strong>the same length</strong>, return <code>true</code> if <code>s2</code> is a scrambled string of <code>s1</code>, otherwise, return <code>false</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s1 = &quot;great&quot;, s2 = &quot;rgeat&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> One possible scenario applied on s1 is:
&quot;great&quot; --&gt; &quot;gr/eat&quot; // divide at random index.
&quot;gr/eat&quot; --&gt; &quot;gr/eat&quot; // random decision is not to swap the two substrings and keep them in order.
&quot;gr/eat&quot; --&gt; &quot;g/r / e/at&quot; // apply the same algorithm recursively on both substrings. divide at random index each of them.
&quot;g/r / e/at&quot; --&gt; &quot;r/g / e/at&quot; // random decision was to swap the first substring and to keep the second substring in the same order.
&quot;r/g / e/at&quot; --&gt; &quot;r/g / e/ a/t&quot; // again apply the algorithm recursively, divide &quot;at&quot; to &quot;a/t&quot;.
&quot;r/g / e/ a/t&quot; --&gt; &quot;r/g / e/ a/t&quot; // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is &quot;rgeat&quot; which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s1 = &quot;abcde&quot;, s2 = &quot;caebd&quot;
<strong>Output:</strong> false
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s1 = &quot;a&quot;, s2 = &quot;a&quot;
<strong>Output:</strong> true
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>s1.length == s2.length</code></li>
	<li><code>1 &lt;= s1.length &lt;= 30</code></li>
	<li><code>s1</code> and <code>s2</code> consist of lowercase English letters.</li>
</ul>

# intuition is that s2 can be scrabled by s1 as long as they have the same letters.

# for example 

# 12345 -> 54321
# 12 / 345
# 12 -> 2 / 1
# 345 -> 5 / 34
# 34 -> 4/3

# oh here is a counter example 

# abcde -> caebd

# abcde -> bcde / a to move c before a

# but now we have no way to move b/d/e after a 

# every scrable moves a substring s1 permanently after s2

# cadbe won't work either, because when you move c before a, you must be moving de before a and no way back

# so the first split must happen between the first letters of s1 and s2, the scramble is promising only when 
# all letter after s2's first letter is always in front of s1's letter

# brute force is to enumerate all scrambled s2, for a string of length n, each split is O(n), and there are n-1 positions to split

# so O(n) = n(n-1)*T(n-1) = O(n^2n)
# theta(n) = n(n-1)*T(n/2) = O(n^(2*log_2^n))


# so basically we can divide and conqure the problem: 

# for s1 = abcde and s2 = cdeba, we have 4 split

# a/bcde, ab/cde, abc/de, abcd/e

# now for s2 to be a scramble string, it must be any of the following split match the those for s1's split

# c/deba, cd/eba, cde/ba, cdeb/a

# by match we means the two part of at least one s2 spllits can be scramble, individualy by the two part of at least one s1 splits
# we know that when letters doesn't match, or length doesn't match, it won't be scramble. This help eliminate many cases. 

# Effectively, we only need to check: 
# a/bcde v.s. c/deba and cdeb/a => i=1, s1[:1] v.s. s2[:i] && s1[1:5] v.s. s2[1:5] | s1[:1] v.s. s2[5-1:5] && s1[1:5] v.s. s2[:5-1]
# ab/cde v.s.  cd/eba and cde/ba
# abc/de v.s. cd/eba and cde/ba
# abcd/e v.s. c/deba and cdeb/a

# and we can also expect many substrings comparison will be repeated and we can memorize for quicker solution.

class Solution:
    @functools.lru_cache(maxsize=1024*1024, typed=False)
    def isScramble(self, s1: str, s2: str) -> bool:
        # print(s1, s2)
        if s1 == s2:
            return True
        if sorted(s1) != sorted(s2):
            return False;
        n = len(s1)
        for i in range(1,n):
            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:n], s2[i:n]):
                return True
            if self.isScramble(s1[:i], s2[n-i:n]) and self.isScramble(s1[i:n], s2[:n-i]):
                return True
        return False

18900