<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>

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        def mm(dct1,dct2):
            mmCnt=0
            for l,cnt in dct1.items():
                try:
                    cnt2=dct2[l]
                except KeyError:
                    cnt2=0
            if cnt>cnt2:            
                mmCnt+=cnt-cnt2
            return mmCnt    

        def count(s):
            dct={}
            for l in s:
                try:
                    dct[l]+=1
                except KeyError:
                    dct[l]=1
            return dct            

        def upd(s,i,dcts):
            l=s[i]
            cnt=dcts[1].pop(l)
            if cnt >1:
                dcts[1][l]=cnt-1
            try:
                dcts[0][l]+=1
            except KeyError:
                dcts[0][l]=1
        def upd2(s,i,dcts):
            #print(dcts)
            l=s[-1-i]
            cnt=dcts[0].pop(l)
            if cnt >1:
                dcts[0][l]=cnt-1
            try:
                dcts[1][l]+=1
            except KeyError:
                dcts[1][l]=1                        

        cache={}
        def check(s1,s2,dct1=None,dct2=None,n=0):
            try:
                r= cache[(s1,s2)]
                #print('   '*n,s1,s2, 'HIT!')
                return r
            except KeyError:
                pass    
               

            #print('   '*n,s1,s2)
            if s1==s2:
                return True
            if dct1 is None:
                dcts1={},count(s1)
                dcts2={},count(s2)
                dcts2x=dcts2[1].copy(),{}

                if dcts1[1]!=dcts2[1]:
                    return False
            else:
                if len(s1)<=3:
                    return True
                dcts1={},dct1.copy()
                dcts2={},dct2.copy()
                dcts2x=dct2.copy(),{}        

            for i in range(0,len(s1)-1):
                upd(s1,i,dcts1)
                upd(s2,i,dcts2)
                upd2(s2,i,dcts2x)
                if dcts1==dcts2:
                    if check(s1[:i+1],s2[:i+1],dcts1[0],dcts2[0]   , n+1 ) and check(s1[i+1:],s2[i+1:],dcts1[1],dcts2[1],n+1):
                        cache[s1,s2]=True
                        return True   
                if dcts1==dcts2x[::-1]:
                    if check( s1[:i+1],s2[-1-i:], dcts1[0],dcts2x[1] , n+1) and check(s1[i+1:],s2[:-1-i],dcts1[1],dcts2x[0],n+1):
                        cache[s1,s2]=True
                        return True
            cache[s1,s2]=False            
            return False            


        return check(s1,s2)


16900