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

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;




class Solution {
public:

bool ismatch(string &s1 , int i ,int j , string &s2)
{
    string s = s2.substr(i,j-i+1);
    if(s1 == s)
    {
        return true;
    }
    return false;
}
map<pair<string,pair<int,int>>,bool> mp;

bool solve(int i , int j , string &s1 , string &s2 )
{
    //cout<<i<<" "<<j<<" -> "<<s1<<endl;

    if(i>j)
    {
        return false;
    }

    if(ismatch(s1,i,j,s2))
    {
        return true;
    }
    if(mp.find({s1,{i,j}}) != mp.end())
    {
        return mp[{s1,{i,j}}];
    }


    for(int k = i;k<j;k++)
    {
        int start_inx = i , end_inx = k;
        string sub_s1 = s1.substr(0,end_inx-start_inx+1);
        string sub_s2 = s1.substr(0 + end_inx-start_inx+1,j-end_inx);
        // keep same 
        //cout<<"same => i = "<<i<<" j = "<<j<<" s1 "<<s1<<endl;
        if(solve(i,end_inx,sub_s1,s2) && solve(end_inx+1,j,sub_s2,s2))
        {
            return mp[{s1,{i,j}}] = true;
        }
        // swap
        //cout<<"swap => i = "<<i<<" j = "<<j<<" s1 "<<s1<<endl;
         int new_start = start_inx, new_end = start_inx + (j-end_inx) -1;
        if(solve( i,new_end ,sub_s2 , s2)  && solve(new_end + 1 , j, sub_s1 , s2))
        {
            return mp[{s1,{i,j}}] = true;
        }
    }

    return  mp[{s1,{i,j}}] =  false;
}

    bool isScramble(string s1, string s2)
    {

        return solve(0,s1.size()-1,s1,s2);
    }
};


28625