将一个单词按照这种方式分：
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 = ; i < len; ++i)
{
string s1_left = s1.substr(,i);
string s1_right = s1.substr(i);
string s2_left = s2.substr(,i);
string s2_right = s2.substr(i);
if (subScramble(s1_left, s2_left) && subScramble(s1_right, s2_right))
return true;
s2_left = s2.substr(, 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);
}
};
如果有更好的方法，我们一般是不用递归的，因为递归往往复杂以致难以掌控。继续学习，发现果然有动态规划的方法。凭空想，确实难以想象。但看见之后又恍然明了。
本题递归复杂度是非多项式的。具体多少您探讨一下。动态规划的复杂度应该是O(n^4)，连动态规划都这个复杂度了，可见此题之可怕啊。
三维动态规划：
dp[k][i][j]: s1的第i个开始长度为k的串和s2的第j个开始长度为k的串是否scrambled，是的话true，否则存false；
同递归核心思想，dp[k][i][j]应该可以从1到k-1长度的分割来求解，一旦有一个为true，那么dp[k][i][j]就为true并跳出。
即：
dp[k][i][j] = (dp[div][i][j] && dp[k-div][i+div][j+div] || dp[div][i][j+k-div] && dp[k-div][i+div][j]);
div从1到k-1，分两种情况，即s1的从i开始的div个和s2从j开始的div个scrambled并且从i+div开始的k-div个都匹配那么true，
同理，如果s1的i开始的div个和s2的后div个匹配以及剩下另外两部分也都匹配，那么true。直到找到true位置。如下代码，找到true后，for中的判断!dp[k][i][j]不成立就跳出了。
class Solution {
public:
// 动态规划 dp[k][i][j]存s1从第i个开始长度为k的串和s2从j开始长度为k的串是否scrambled
bool isScramble(string s1, string s2)
{
if (s1.size() != s2.size()) return false;
int len = s1.size();
bool dp[len+][len][len];
// initialization
for (int i = ; i < len; ++i)
for (int j = ; j < len; ++j)
dp[][i][j] = s1[i] == s2[j];
// dp
for (int k = ; k < len + ; ++k)
for (int i = ; i < len; ++i)
for (int j = ; j < len; ++j)
{
// initialization
dp[k][i][j] = false;
// once dp[k][i][j] is true, jump out
for (int div = ; div < k && !dp[k][i][j]; ++div)
dp[k][i][j] = (dp[div][i][j] && dp[k-div][i+div][j+div] || dp[div][i][j+k-div] && dp[k-div][i+div][j]);
}
return dp[len][][];
}
};
以下三点值得注意：
1. 此题递归只要主要判断排序后子串是否相等，不等直接剪枝，减少计算量。
2. 两中方法都用到的核心是把两个字符串都分成两部分，如果对应匹配或者交叉匹配满足，则true。
3. 就是substr的用法，如何准确判断子串。