<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 {
public:
    int solve(vector<vector<vector<int>>>& dp,string s1, string s2, int i, int j, int len){
        if(len<=0){
            return 1;
        }
        if(s1.size()<i+len){
            return 0;
        }
        if(s2.size()<j+len){
            return 0;
        }
        if(len==1){
            return s1[i]==s2[j];
        }
        if(dp[i][j][len]!=-1){
            return dp[i][j][len];
        }
        int ans=0;
        vector<int> a1(26,0),a2(26,0);
        for(int k=0;k<len;k++){
            a1[s1[i+k]-'a']++;
            a2[s2[j+k]-'a']++;
        }
        for(int k=0;k<26;k++){
            if(a1[k]!=a2[k]){
                ans=-1;
                break;
            }
        }
        if(ans==-1){
            ans=0;
            dp[i][j][len]=ans;
            return ans;
        }
        for(int k=0;k<len;k++){
            if(s1[i+k]!=s2[j+k]){
                ans=0;
                break;
            }
            else{
                ans=1;
            }
        }
        if(ans==1){
            dp[i][j][len]=1;
            //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
            return ans;
        }
        for(int k=1;k<=len/2;k++){
            int a=solve(dp,s1,s2,i,j,k),b=solve(dp,s1,s2,i+k,j+k,len-k);
            if(a==1 && b==1){
                ans=1;
                break;
            }
            int c=solve(dp,s1,s2,i,j+len-k,k),d=solve(dp,s1,s2,i+k,j,len-k);
            if(c==1 && d==1){
                ans=1;
                break;
            }
            int e=solve(dp,s1,s2,i+len-k,j,k),f=solve(dp,s1,s2,i,j+k,len-k);
            if(e==1 && f==1){
                ans=1;
                break;
            }
            int g=solve(dp,s1,s2,i+len-k,j+len-k,k),h=solve(dp,s1,s2,i,j,len-k);
            if(g==1 && h==1){
                ans=1;
                break;
            }
        }
        dp[i][j][len]=ans;
        //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
        return ans;
    }
    bool isScramble(string s1, string s2) {
        int n=s1.size();
        vector<vector<vector<int>>> dp(n,vector<vector<int>>(n,vector<int>(n+1,-1)));
        return solve(dp,s1,s2,0,0,n);
    }
};
33814