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

from functools import lru_cache
import time
class Solution:
    cache = {}
    def isScramble2(self, s1: str, s2: str) -> bool:        
        def hashmatch(s1map, s2):
            s2map = {}
            for s in s2:
                if s not in s2map:
                    s2map[s] = 1
                else:
                    s2map[s] += 1
            for key in s1map.keys():
                if key not in s2map or s2map[key] != s1map[key]:
                    return False
            return True            
        if len(s1) == 1:
            return s1 == s2
        key = f'{s1}-{s2}'
        if key in self.cache:
            return self.cache[key]
        n = len(s1)
        for i in range(n):
            if i+1<n-i-1:
                s1_l = s1[:i+1]
                s2_l = s2[:i+1]
                s1_r = s1[i+1:]
                s2_r = s2[i+1:]
                s1map = {}
                for s in s1_l:
                    if s not in s1map:
                        s1map[s] = 1
                    else:
                        s1map[s] += 1
                s1rmap = {}
                for s in s1_r:
                    if s not in s1rmap:
                        s1rmap[s] = 1
                    else:
                        s1rmap[s] += 1
                if hashmatch(s1map, s2_l) and hashmatch(s1rmap, s2_r):
                    if self.isScramble(s1_l, s2_l) and self.isScramble(s1_r, s2_r):
                        self.cache[key] = True
                        return True
                s1_l = s1[:i+1]
                s2_l = s2[-i-1:]
                s1_r = s1[i+1:]
                s2_r = s2[:-i-1]
                if hashmatch(s1map, s2_l) and hashmatch(s1rmap, s2_r):
                    if self.isScramble(s1_l, s2_l) and self.isScramble(s1_r, s2_r):
                        self.cache[key] = True
                        return True
            else:
                s1_l = s1[i+1:]
                s2_l = s2[i+1:]
                s1_r = s1[:i+1]
                s2_r = s2[:i+1]
                s1map = {}
                for s in s1_l:
                    if s not in s1map:
                        s1map[s] = 1
                    else:
                        s1map[s] += 1
                s1rmap = {}
                for s in s1_r:
                    if s not in s1rmap:
                        s1rmap[s] = 1
                    else:
                        s1rmap[s] += 1                
                if hashmatch(s1map, s2_l) and hashmatch(s1rmap, s2_r):
                    if self.isScramble(s1_l, s2_l) and self.isScramble(s1_r, s2_r):
                        self.cache[key] = True
                        return True            
                s1_l = s1[i+1:]
                s2_l = s2[:-i-1]
                s1_r = s1[:i+1]
                s2_r = s2[-i-1:]
                if hashmatch(s1map, s2_l) and hashmatch(s1rmap, s2_r):
                    if self.isScramble(s1_l, s2_l) and self.isScramble(s1_r, s2_r):
                        self.cache[key] = True
                        return True                
        self.cache[key] = False
        return False

    def isScramble(self, s1: str, s2: str) -> bool:
        from functools import lru_cache

        @lru_cache(None)
        def dfs(s1, s2):
            if s1 == s2:
                return True
            if sorted(s1) != sorted(s2):
                return False
            n = len(s1)
            for i in range(1, n):
                # Check without swap
                if dfs(s1[:i], s2[:i]) and dfs(s1[i:], s2[i:]):
                    return True
                # Check with swap
                if dfs(s1[:i], s2[-i:]) and dfs(s1[i:], s2[:-i]):
                    return True
            return False

        return dfs(s1, s2)    
17700