<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 {
  // Problem says max length == 30
  unsigned char dp[31][31][31];
  std::string s1, s2;

public:
  bool inner(int s1idx, int s2idx, int size) {
    unsigned char &entry = dp[size-1][s1idx][s2idx];
    if(entry != 0xFF) {
      return entry == 1;
    }

    if(memcmp(&s1[s1idx], &s2[s2idx], size) == 0) {
      entry = 1;
      return true;
    }    

    int counts[26] = {0};
    memset(counts, 0, sizeof(counts));
    for(int i = 0; i < size; ++i) {
      ++counts[s1[s1idx+i]-'a'];
      --counts[s2[s2idx+i]-'a'];
    }
    
    for(int i = 0; i < 26; ++i) {
      if(counts[i] != 0) {
        entry = 0;
        return false;
      }
    }

    // We checked above to ensure the char counts are equal
    if(size == 1) {
      entry = 1;
      return true;
    }
    
    for(int left_size = 1; left_size < size; ++left_size) {
      int right_size = size - left_size;
      if(inner(s1idx, s2idx, left_size) &&
         inner(s1idx+left_size, s2idx+left_size, right_size)) {
         entry = 1;
         return true;
      }
      if(inner(s1idx, s2idx+right_size, left_size) &&
         inner(s1idx+left_size, s2idx, right_size)) {
         entry = 1;
         return true;
      }
    }
    entry = 0;
    return false;
  }


  bool isScramble(std::string s1_, std::string s2_)
  {
    // Initialize dp array
    memset(dp, 0xFF, sizeof(dp));

    // Initialize strings
    s1 = std::move(s1_);
    s2 = std::move(s2_);

    return inner(0, 0, s1.size());
  }
};
10094