题目描述为：
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 ifs2 is a scrambled string of
s1.
====================================
第一反应模拟肯定是不可能的，再仔细看scramble实际就是选取一个节点然后旋转，所以明显对一个节点旋转两次必定是一样的。
如果能把大问题化成递归的小问题那就好解决了。
1.首先我们看例子中的"great" 它的旋转只能是分成两半：要么这两半交换位置要么不交换，如题中可以看出是gr 为一半，eat为一半，在结果子串"rgate"可以看到两半的相对位置是没有改变的。于是我们可以递归地检查前一半的两个子串是否是合法的，以及后一半是否是合法的；当均只有一个字符的时候直接比较是否相等。
但也有可能两半相对位置有变化： 比如 s1="gr | eat" ，s2=" ate | rg"，可以看到两半相对位置有变化，这时我们需要递归检查s1前一半和s2后一半是否合法，以及s1后一半和s2前一半是否合法。
2.刚开始被题目误导了还以为是二分，实际上不是，我们必须枚举所有分法比如 s1 = "g | reat" = "gr | eat " = "gre | at" = "grea | t ”，每一种都要检查一次，当然如果哪一次检查成功了就可以直接返回了。
3.在确定了分半之后，我们还需要检查s1跟s2中分半的对应问题，即是前一半对后一半还是后一半对前一半，这个好解决，因为题目保证两个子串字符相同只是位置不同，所以加入我们当前假设分半是 'gr | eat" ，我们只需要为前一半建立出现次数记录，然后检查s2中前一半出现的字符是否跟它一样，如果是那就是前一半对前一半；同理我们也可以检查是否是前一半对后一半，注意这两种情况并非是互斥的，可能两种都符合，但是只有一种是合理的，所以两种对应都要检查。
4.代码： 44ms过大集合
#include<iostream>
#include<vector>
#include<string>
#include<cassert>
using namespace std;
bool containAll(const string& s1,int st1,int end1,const string& s2,int st2,int end2)
{
vector<int> visit(256,0);
int len=end1-st1+1;
for(int i=0;i<len;i++)
visit[s1[st1+i]]++;
bool ans=true;
for(int i=0;i<len;i++)
{
if (visit[s2[st2+i]]<=0)
{
ans=false;
break;
}
visit[s2[st2+i]]--;
}
return ans;
}
bool isOK(string& s1,int st1,int end1,string& s2,int st2,int end2)
{
if (st1>end1 && st2>end2)
return true;
if (st1==end1&&st2==end2)
return s1[st1]==s2[st2];
bool ans=false;
for(int len=1;len<=(end1-st1);len++)
{
int right=end1-st1+1-len;
int loc=st2;
if (containAll(s1,st1,st1+len-1,s2,st2,st2+len-1))
{
ans= isOK(s1,st1,st1+len-1,s2,st2,st2+len-1)&&isOK(s1,st1+len,end1,s2,st2+len,end2);
}
if (ans)
break;
if (containAll(s1,st1,st1+right-1,s2,st2+len,end2))
{
ans= isOK(s1,st1,st1+right-1,s2,st2+len,end2)&&isOK(s1,st1+right,end1,s2,st2,st2+len-1);
}
if (ans)
break;
}
return ans;
}
bool isScramble(string s1,string s2)
{
int sz1=s1.size();
int sz2=s2.size();
if (sz1!=sz2) return false;
return isOK(s1,0,sz1-1,s2,0,sz2-1);
}
int main()
{
string s1,s2;
while((cin>>s1)&&s1.compare("-1")!=0)
{
cin>>s2;
bool ans=isScramble(s1,s2);
cout<<ans<<endl;
}
}