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

// 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;
}

// 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);
}

dp[len][i][j]: 代表s1[i...i + len - 1]和s2[j...j + len - 1]是否為scramble strings。

// 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];
}