<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:
    map<pair<string, string>, bool> dp; 

    bool solve(string s1 , string s2){
        int n = s1.length() ;

        if(s1 == s2){
            return true ;
        }
        if(n == 1){ 
            return false ;
        }

        if(dp.find({s1 , s2}) != dp.end()){
            return dp[{s1 , s2}] ;
        }

        
        for(int i = 1 ; i < n ; i++){
            if(solve(s1.substr(0 , i) , s2.substr(0 , i)) && solve(s1.substr(i) , s2.substr(i))){
                return dp[{s1 , s2}] = true ;
            }

            if(solve(s1.substr(0,i) , s2.substr(n-i)) && solve(s1.substr(i) , s2.substr(0,n-i))){
                return dp[{s1 , s2}] = true ;
            }
        }

        return dp[{s1 , s2}] = false ; 
    }
    bool isScramble(string s1, string s2) {
        dp.clear() ;
        return solve(s1 , s2) ;
    }
};


// class Solution {
// public:
//     // Memoization table to store the results of subproblems
//     map<pair<string, string>, bool> dp;

//     // Helper function to check if two strings have the same character frequency
//     bool hasSameCharacterFrequency(const string& s1, const string& s2) {
//         vector<int> count(26, 0);
//         for (char c : s1) count[c - 'a']++;
//         for (char c : s2) count[c - 'a']--;
//         return all_of(count.begin(), count.end(), [](int x) { return x == 0; });
//     }

//     bool solve(string s1, string s2) {
//         // Base case: if both strings are equal, they are scrambled versions
//         if (s1 == s2) return true;

//         // If lengths are not equal, they can't be scrambled versions
//         if (s1.length() != s2.length()) return false;

//         // Check memoized results
//         if (dp.find({s1, s2}) != dp.end()) return dp[{s1, s2}];

//         // Pruning: If s1 and s2 don't have the same character frequency, they can't be scrambled versions
//         if (!hasSameCharacterFrequency(s1, s2)) {
//             return dp[{s1, s2}] = false;
//         }

//         int n = s1.length();
//         // Try every possible split position
//         for (int i = 1; i < n; i++) {
//             // Case 1: Direct split check (s1[0:i] with s2[0:i] and s1[i:n] with s2[i:n])
//             if (solve(s1.substr(0, i), s2.substr(0, i)) && solve(s1.substr(i), s2.substr(i))) {
//                 return dp[{s1, s2}] = true;
//             }
//             // Case 2: Cross split check (s1[0:i] with s2[n-i:n] and s1[i:n] with s2[0:n-i])
//             if (solve(s1.substr(0, i), s2.substr(n-i)) && solve(s1.substr(i), s2.substr(0, n-i))) {
//                 return dp[{s1, s2}] = true;
//             }
//         }

//         // If no valid scramble found, return false
//         return dp[{s1, s2}] = false;
//     }

//     bool isScramble(string s1, string s2) {
//         // Clear the memoization table
//         dp.clear();

//         // Start the recursive check
//         return solve(s1, s2);
//     }
// };

30849