将一个单词按照这种方式分：

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".

这样就说他们是scrambled string。现在给你两个字符串怎么判断是否属于scrambled string呢

思路：

想了n久，木有什么好的idea。

然后学习了justdoit兄的博客，理解了后自己也跟着写了个递归的。

简单的说，就是s1和s2是scramble的话，那么必然存在一个在s1上的长度l1，将s1分成s11和s12两段，同样有s21和s22。
那么要么s11和s21是scramble的并且s12和s22是scramble的；
要么s11和s22是scramble的并且s12和s21是scramble的。

判断剪枝是必要的，否则过不了大数据集合。

class Solution {public:bool subScramble(string s1, string s2){    if (s1 == s2) return true;    int len = s1.size();    string sort_s1 = s1, sort_s2 = s2;    sort(sort_s1.begin(), sort_s1.end());    sort(sort_s2.begin(), sort_s2.end());    if (sort_s1 != sort_s2) return false; //如果字母不相等直接返回错误    for (int i = 1; i < len; ++i)    {        string s1_left = s1.substr(0,i);        string s1_right = s1.substr(i);        string s2_left = s2.substr(0,i);        string s2_right = s2.substr(i);        if (subScramble(s1_left, s2_left) && subScramble(s1_right, s2_right))            return true;        s2_left = s2.substr(0, len - i);        s2_right = s2.substr(len - i);        if (subScramble(s1_left, s2_right) && subScramble(s1_right, s2_left))            return true;    }    return false;}bool isScramble(string s1, string s2){    return subScramble(s1, s2);}};

leetcode[86] Scramble String