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

给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。

下图是字符串 s1 = "great" 的一种可能的表示形式。

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t
在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。

例如，如果我们挑选非叶节点 "gr" ，交换它的两个子节点，将会产生扰乱字符串 "rgeat" 。

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t
我们将 "rgeat” 称作 "great" 的一个扰乱字符串。

同样地，如果我们继续将其节点 "eat" 和 "at" 进行交换，将会产生另一个新的扰乱字符串 "rgtae" 。

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a
我们将 "rgtae” 称作 "great" 的一个扰乱字符串。

给出两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。

示例 1:

输入: s1 = "great", s2 = "rgeat"
输出: true
示例 2:

输入: s1 = "abcde", s2 = "caebd"
输出: false

解题思路：

参考Grandyang的博客

这道题定义了一种搅乱字符串，就是说假如把一个字符串当做一个二叉树的根，然后它的非空子字符串是它的子节点，然后交换某个子字符串的两个子节点，重新爬行回去形成一个新的字符串，这个新字符串和原来的字符串互为搅乱字符串。这道题可以用递归 Recursion 或是动态规划 Dynamic Programming 来做，我们先来看递归的解法，参见网友 uniEagle 的博客，简单的说，就是s1和s2是 scramble 的话，那么必然存在一个在 s1 上的长度 l1，将 s1 分成 s11 和 s12 两段，同样有 s21 和 s22，那么要么 s11 和 s21 是 scramble 的并且 s12 和 s22 是 scramble 的；要么 s11 和 s22 是 scramble 的并且 s12 和 s21 是 scramble 的。就拿题目中的例子 rgeat 和 great 来说，rgeat 可分成 rg 和 eat 两段， great 可分成 gr 和 eat 两段，rg 和 gr 是 scrambled 的， eat 和 eat 当然是 scrambled。

递归写法：
class Solution {
public:
    bool isScramble(string s1, string s2) 
    {
        if(s1.size() != s2.size()) return false ;
        if(s1 == s2) return true ;
        
        string str1 = s1 ;
        string str2 = s2 ;
        sort(str1.begin() , str1.end()) ;
        sort(str2.begin() , str2.end()) ;
        if(str1 != str2) return false ;
        
        for(int i = 1 ; i < s1.size() ; ++i)
        {
            string s11 = s1.substr(0 , i) ;
            string s12 = s1.substr(i) ;
            string s21 = s2.substr(0 , i) ;
            string s22 = s2.substr(i) ;
            if(isScramble(s11 , s21) && isScramble(s12 , s22)) return true ;
            s22 = s2.substr(s2.size() - i) ;
            s21 = s2.substr(0 , s2.size() - i) ;
            if(isScramble(s11 , s22) && isScramble(s12 , s21)) return true ;
        }
        
        return false ;
    }
};

动态规划/迭代写法
class Solution {
public:
    bool isScramble(string s1, string s2) 
    {
        if(s1.size() != s2.size()) return false ;
        if(s1 == s2) return true ;
        int sz = s1.size() ;
        
        vector<vector<vector<bool>>> dp(sz , vector<vector<bool>>(sz , vector<bool>(sz + 1 , false))) ;
        
        for(int i = 0 ; i < sz ; ++i)
        {
            for(int j = 0 ; j < sz ; ++j)
            {
                if(s1[i] == s2[j]) dp[i][j][1] = true ;
            }
        }
        
        for(int len = 2 ; len <= sz ; len++)
        {
            for(int i = 0 ; i <= sz - len ; ++i)
            {
                for(int j = 0 ; j <= sz - len ; ++j)
                {
                    for(int l = 1 ; l < len ; ++l)
                    {
                        if((dp[i][j][l] && dp[i + l][j + l][len - l]) || (dp[i][j + len - l][l] && dp[i + l][j][len - l])) 
                        {
                            dp[i][j][len] = true ;
                            break ;
                        }
                    }
                }
            }
        }
        
        return dp[0][0][sz] ; 
    }
};