# 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

# Solution

Approach 1: memoized recursion (with early stopping).

Approach 2: 3D DP.

# Code (Python)

Approach 1:

    def isScramble(self, s1: str, s2: str) -> bool:
        # memoized recursion with early stopping
        return self._is_scramble(s1, s2, {})
    
    def _is_scramble(self, s1, s2, memo):
        if s1 > s2: # enforce an ordering of the key
            s1, s2 = s2, s1
        if (s1, s2) in memo:
            return memo[(s1, s2)]
        if s1 == s2:
            memo[(s1, s2)] = True
            return True
        # early stopping
        if sorted(s1) != sorted(s2):
            memo[(s1, s2)] = False
            return False
        for i in range(1, len(s1)):
            if self._is_scramble(s1[:i], s2[:i], memo) and self._is_scramble(s1[i:], s2[i:], memo):
                memo[(s1, s2)] = True
                return True
            if self._is_scramble(s1[:i], s2[-i:], memo) and self._is_scramble(s1[i:], s2[:-i], memo):
                memo[(s1, s2)] = True
                return True
        memo[(s1, s2)] = False
        return False

Approach 2:

    def isScramble(self, s1: str, s2: str) -> bool:
        # DP -- scramble[i][j][k]: s1[i:i+k] and s2[j:j+k] is scramble (substring of length k, starting at position i and j for s1 and s2)
        # scramble[i][j][k] = (scramble[i][j][l] and scramble[i+l][j+l][k-l]) or (scramble[i][j+k-l][l] and scramble[i+l][j][k-l])
        scramble = [[[False] * (len(s1) + 1) for _ in range(len(s1))] for _ in range(len(s1))]
        for k in range(1, len(s1) + 1):
            for i in range(len(s1) - k + 1):
                for j in range(len(s1) - k + 1):
                    if k == 1:
                        scramble[i][j][k] = s1[i] == s2[j]
                    else:
                        is_scramble = False
                        for l in range(1, k):
                            if (scramble[i][j][l] and scramble[i+l][j+l][k-l]) or (scramble[i][j+k-l][l] and scramble[i+l][j][k-l]):
                                is_scramble = True
                                break
                        scramble[i][j][k] = is_scramble
        
        return scramble[0][0][len(s1)]

# Code (C++)

Approach 1:

// stack-overflow
class Solution {
private:
    unordered_map<string,bool> umap;
public:
    bool isScramble(string s1, string s2) {
        int n = s1.size();
        if (n != s2.size())
            return false;
        if (n == 1)
            return s1 == s2;
        if (s1 == s2)
            return true;
        if (s1 > s2) // enforce an ordering of the key
        {
            std::swap(s1, s2);
        }
        string key = s1 + "," + s2;
        if (umap.find(key) != umap.end())
            return umap[key];
        // early stopping
        string tmp1 = s1;
        string tmp2 = s2;
        std::sort(tmp1.begin(), tmp1.end());
        std::sort(tmp2.begin(), tmp2.end());
        if (tmp1 != tmp2)
        {
            umap[key] = false;
            return false;
        }
        for (int len = 1; len <= n; ++len)
        {
            if (isScramble(s1.substr(0, len), s2.substr(0, len)) &&
                isScramble(s1.substr(len, n-len), s2.substr(len, n-len))
                ||
                isScramble(s1.substr(0, len), s2.substr(n-len, len)) &&
                isScramble(s1.substr(len, n-len), s2.substr(0, n-len)))
            {
                umap[key] = true;
                return true;
            }
        }
        umap[key] = false;
        return false;
    }
};

Approach 2:

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int n = s1.size();
        if (n != s2.size())
            return false;
        int match[n+1][n][n];
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                match[1][i][j] = (s1[i] == s2[j]);
            }
        }
        for (int len = 2; len <= n; ++len)
        {
            for (int i = 0; i+len <= n; ++i)
            {
                for (int j = 0; j+len <= n; ++j)
                {
                    for (int k = 1; k < len; ++k)
                    {
                        match[len][i][j] =
                            (match[k][i][j] && match[len-k][i+k][j+k]) ||
                            (match[k][i][j+len-k] && match[len-k][i+k][j]);
                        if (match[len][i][j])
                            break;
                    }
                }
            }
        }
        return match[n][0][0];
    }
};