问题描述：
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.
算法分析：这个问题是字符串树通过交换叶子节点变形的。而不是简单地只要字母相同就行了。有两种方法，一种是递归，另一种是动态规划。
递归法：把s1，s2分别分成两部分，判断s1的两部分和s2的两部分是否分别可以交换相等。
//递归法
public boolean isScramble(String s1, String s2)
{
if(s1.length() != s2.length())
{
return false;
}
if(s1.equals(s2))
{
return true;
}
/*
char[] c1 = s1.toCharArray();
Arrays.sort(c1);
char[] c2 = s2.toCharArray();
Arrays.sort(c2);
if(!Arrays.equals(c1, c2))
{
return false;
}
**/
for(int i = 1; i < s1.length(); i ++)//i从1开始，否则i=0将无限递归
{
if(isScramble(s1.substring(0, i), s2.substring(0, i))
&& isScramble(s1.substring(i), s2.substring(i)))
{
return true;
}
if(isScramble(s1.substring(0, i), s2.substring(s2.length() - i))
&&(isScramble(s1.substring(i), s2.substring(0, s2.length()-i ))))
{
return true;
}
}
return false;
}
动态规划：
这道题用二维数组来存储中间结果已经不行了，需要一个三维数组 dp[i][j][len]，表示从s1的第i个字符开始长度为len的子串，和从s2的第j个字符开始长度为len的子串，是否互为scramble。
初始化为dp[i][j][1] = s1.charAt(i) == s2.charAt(j)，即长度为1的子串是否互为scramble。
三维数组就要三层循环，最终结果为dp[0][0][s1.length()]，即从s1的第0个字符开始长度为s1.length()的子串，即s1本身和s2本身是否互为scramble。
要判断dp[i][j][len]的值，就要把s1从i开始长度为len的串分别从k=1, 2 ... len-1处切开，判断切成的两半和s2同样切成的两半是否互为scramble，只要有一种切法满足条件，那么dp[i][j][len]就为true，否则为false。
//动态规划
public boolean isScramble2(String s1, String s2)
{
if(s1.equals(s2)) return true;
if(s1.length() != s2.length()) return false;
//dp[i][j][len]代表s1从i，s2从j开始，长为len的字符串是否为scramble
boolean[][][] dp = new boolean[s1.length()][s2.length()][s1.length()+1];
for(int i = 0; i < s1.length(); i ++)
{
for(int j = 0; j < s2.length(); j ++)
{
dp[i][j][1] = (s1.charAt(i) == s2.charAt(j));
}
}
for(int len = 2; len < s1.length() + 1; len ++)
{
for(int i = 0; i < s1.length()- len + 1; i ++)
{
for(int j = 0; j < s2.length() - len + 1; j ++)
{
for(int k = 1; k < len; k ++)
{
dp[i][j][len] |= (dp[i][j][k] && dp[i+k][j+k][len-k]) ||
(dp[i][j+len-k][k] && dp[i+k][j][len-k]);
}
}
}
}
return dp[0][0][s1.length()];
}