哎，难题又不会做，

思路没有什么难度，

关键是要把问题思考透彻，

要考虑的要点还是挺多的，不容易一下子都考虑到；

我开始的思路是按照树的根去递归的，

这样就必须要没有重复元素，因为需要每次在s2中查找s1中的元素；

怎么说呢，有点考虑的过于specific了，其实直接把字符串分成两部分递归就可以了，

不过需要注意不能漏掉两部分可能次序调换的情况。

1 class Solution { 2 public: 3     bool isScramble(string s1, string s2) { 4         // Start typing your C/C++ solution below 5         // DO NOT write int main() function 6         if (s1.empty() && s2.empty()) { 7             return true; 8         } 9         if (s1 == s2) {10             return true;11         }12         return scramble(s1, 0, s1.size() - 1, s2, 0, s2.size() - 1);13     }14     bool scramble(string &s1, int b1, int e1, string &s2, int b2, int e2) {15         if (!same(s1, b1, e1, s2, b2, e2)) {16             return false;17         }18         int len = e1 - b1 + 1;19         if (len == 0) {20             return true;21         }22         if (len == 1) {23             return (s1[b1] == s2[b2]);24         }25         for (int i = 0; i < len - 1; ++i) {26             if ((scramble(s1, b1, b1 + i, s2, b2, b2 + i) && scramble(s1, b1 + i + 1, e1, s2, b2 + i + 1, e2)) || 27                 (scramble(s1, b1, b1 + i, s2, e2 - i, e2)) && scramble(s1, b1 + i + 1, e1, s2, b2, e2 - i - 1)) {28                 return true;29             }30         }31         return false;32     }33     bool same(string &s1, int b1, int e1, string &s2, int b2, int e2) {34         vector
     
       count(256, 0);35         for (int i = b1; i <= e1; ++i) {36             ++count[s1[i]];37         }38         for (int i = b2; i <= e2; ++i) {39             --count[s2[i]];40         }41         for (int i = 0; i < 256; ++i) {42             if (count[i] != 0) {43                 return false;44             }45         }46         return true;47     }48 };