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.
递归求解，需要剪枝，不然TLE
假设字符串s1：abc与s2：def，依次比较a与d是否可以并且bc与ef是否可以，或者是a与ef是否可以并且bc与d是否可以，然后循环比较ab与de是否可以并且c与f是否可以，或者是ab与d是否可以并且c与ef是否可以，只要有一组成立则abc成立
剪枝：对字符串s1与s2，如果其中有字符不一样，则不需要进行比对了，直接return false
class Solution {
public:
bool isScramble(string s1, string s2) {
if(s1.size()!=s2.size())return false;
if(s1==s2)return true;
string t1=s1,t2=s2;
sort(t1.begin(),t1.end());
sort(t2.begin(),t2.end());
if(t1!=t2)return false;
for(int i=1;i<s1.size();i++){
if((isScramble(s1.substr(0,i),s2.substr(0,i))&&isScramble(s1.substr(i),s2.substr(i)))
||(isScramble(s1.substr(0,i),s2.substr(s2.size()-i))&&isScramble(s1.substr(i),s2.substr(0,s2.size()-i))))
return true;
}
return false;
}
};
原文：http://blog.csdn.net/starcuan/article/details/18710171