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

enum MemoizationResult
{
    UNSET = 0,
    TRUE,
    FALSE
};

class Solution
{
    // length->s1_index->s2_index->isScrambled
    vector<vector<vector<MemoizationResult>>> mMemoization;
    const char *mS1Start = nullptr;
    const char *mS2Start = nullptr;

public:
    bool isLetterCountEqual(const string_view &s1, const string_view &s2)
    {
        // Clock c("isLetterCountEqual");
        constexpr size_t lettercount = 'z' - 'a' + 1;
        vector<int> count1(lettercount, 0);
        vector<int> count2(lettercount, 0);
        for (const char &c : s1)
        {
            count1[c - 'a']++;
        }
        for (const char &c : s2)
        {
            count2[c - 'a']++;
        }
        for (int i = 0; i < lettercount; i++)
        {
            if (count1[i] != count2[i])
            {
                return false;
            }
        }
        return true;
    }
    bool letterCountApproxEqual(const string_view &s1, const string_view &s2)
    {
        // Clock c("letterCountApproxEqual");
        // Sum of letters approximation to know if both contain the same letters.
        return reduce(s1.begin(), s1.end()) == reduce(s2.begin(), s2.end());
    }

    // Return if s2 is a scrambled string of s1
    bool isScramble(string s1, string s2)
    {
        size_t size = s1.size();
        if (size != s2.size())
            return false;
        this->mS1Start = s1.c_str();
        this->mS2Start = s2.c_str();
        this->mMemoization = vector<vector<vector<MemoizationResult>>>(size,
                                                                       vector<vector<MemoizationResult>>(size, vector<MemoizationResult>(size, MemoizationResult::UNSET)));
        string_view sv1{s1};
        string_view sv2{s2};
        return isScramble(sv1, sv2);
    }

private:
    bool isScramble(string_view &s1, string_view &s2)
    {
        size_t size = s1.size();
        // heuristically compare letter numbers for long strings
        if (size == 1)
            return s1[0] == s2[0];
        if (!letterCountApproxEqual(s1, s2) || !isLetterCountEqual(s1, s2))
            return false;
        auto &memoizationRef = this->mMemoization[size-1][s1.data() - mS1Start][s2.data() - mS2Start];
        if (memoizationRef != MemoizationResult::UNSET)
            return memoizationRef == MemoizationResult::TRUE;

        for (int i = 1; i < size; i++)
        {
            auto remainder = size - i;
            // divide s1 into AB where A is of size i and B is of size remainder
            // then compare to CD or EF where C&F are of size i, and D&E are of size remainder in s2.
            auto A = s1.substr(0, i);
            auto B = s1.substr(i, remainder);
            auto C = s2.substr(0, i);
            auto D = s2.substr(i, remainder);
            if (isScramble(A, C) && isScramble(B, D))
            {
                memoizationRef = MemoizationResult::TRUE;
                return true;
            }
            auto E = s2.substr(0, remainder);
            auto F = s2.substr(remainder, i);
            if (isScramble(A, F) && isScramble(B, E))
            {
                memoizationRef = MemoizationResult::TRUE;
                return true;
            }
        }
        memoizationRef = MemoizationResult::FALSE;
        return false;
    }
};

21954