# 87. Scramble String

Given a string *s1*, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of *s1* = `"great"`:

```
    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t
```

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node `"gr"` and swap its two children, it produces a scrambled string `"rgeat"`.

```
    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t
```

We say that `"rgeat"` is a scrambled string of `"great"`.

Similarly, if we continue to swap the children of nodes `"eat"` and `"at"`, it produces a scrambled string `"rgtae"`.

```
    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a
```

We say that `"rgtae"` is a scrambled string of `"great"`.

Given two strings *s1* and *s2* of the same length, determine if *s2* is a scrambled string of *s1*.

**Example 1:**

```
Input: s1 = "great", s2 = "rgeat"
Output: true
```

**Example 2:**

```
Input: s1 = "abcde", s2 = "caebd"
Output: false
```

```cpp
// Brute Force Recursion
bool isScramble(string s1, string s2) { // time: O(5^n); space: O(n)
    if (s1 == s2) return true;
    int len = s1.length();
    vector<int> count(26);
    // characters check
    for (int i = 0; i < len; ++i) {
        ++count[s1[i] - 'a'];
        --count[s2[i] - 'a'];
    }
    for (int cnt : count) {
        if (cnt != 0) return false;
    }
    for (int i = 1; i < len; ++i) {
        if (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i))) return true;
        if (isScramble(s1.substr(0, i), s2.substr(len - i)) && isScramble(s1.substr(i), s2.substr(0, len - i))) return true;
    }
    return false;
}
```

```cpp
// Recursion with Memoization to avoid duplicate calculation
bool helper(const string& s1, const string& s2, unordered_map<string, bool>& memo) {
    bool res = false;
    int len = s1.length();
    if(len == 0) return true;
    if (memo.count(s1 + s2)) return memo[s1 + s2];
    if (s1 == s2) res = true;
    else {
        for (int i = 1; i < len; ++i) {
            res = res || 
                helper(s1.substr(0, i), s2.substr(0, i), memo) && helper(s1.substr(i), s2.substr(i), memo) ||
                helper(s1.substr(0, i), s2.substr(len - i), memo) && helper(s1.substr(i), s2.substr(0, len - i), memo);
        }
    }
    return memo[s1 + s2] = res;
}
bool isScramble(string s1, string s2) {
    unordered_map<string, bool> memo;
    return helper(s1, s2, memo);
}
```

{% hint style="info" %}
dp\[len]\[i]\[j]: 代表s1\[i...i + len - 1]和s2\[j...j + len - 1]是否為scramble strings。
{% endhint %}

```cpp
// Dynamic Programming
bool isScramble(string s1, string s2) { // time: O(n^4); space: O(n^3)
    int len = s1.length();
    if (len == 0) return true;
    if (len == 1) return s1 == s2;
    vector<vector<vector<bool> > > dp(len + 1, vector<vector<bool> >(len, vector<bool>(len, false) ) );
    for (int i = 0; i < len; ++i) {
        for (int j = 0; j < len; ++j) {
            dp[1][i][j] = s1[i] == s2[j];
        }
    }
    for (int l = 2; l <= len; ++l) {
        for (int i = 0; i <= len - l; ++i) {
            for (int j = 0; j <= len - l; ++j) {
                for (int k = 1; k < l && !dp[l][i][j]; ++k) {
                    // dp[l][i][j] = dp[l][i][j] || (dp[k][i][j] && dp[l - k][i + k][j + k]);
                    // dp[l][i][j] = dp[l][i][j] || (dp[k][i + l - k][j] && dp[l - k][i][j + k]);
                    if ((dp[k][i][j] && dp[l - k][i + k][j + k]) || (dp[k][i + l - k][j] && dp[l - k][i][j + k]))
                        dp[l][i][j] = true;
                }
            }
        }
    }
    return dp[len][0][0];
}
```