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.
思路：这一天假设理解思想之后去做感觉不是非常难。可是在想到解法之前还是有一定难度。
本题解法为递归解法，动态规划解法没有掌握。
递归的思路和遍历字符串，切割成两部分，对照两部分能否scramble，只是本题要比較前前和前后两次。
详细代码例如以下：
public class Solution {
public boolean isScramble(String s1, String s2) {
/**
* 思想是递归，将字符串逐个的分为两串
* 然后让两串的前前比較、后后比較，是则返回true
* 不是着前后比較。是则返回true
* 假设还不是。则分割的字符串位置+1
*/
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
//调用函数推断
if(isScr(c1, c2, 0, c1.length, 0, c2.length)){
return true;
}
return false;
}
boolean isScr(char[] c1,char[] c2,int start1,int end1,int start2, int end2){
//推断字符是否为空
if(end1 - start1 <= 0 && end2 - start2 <= 0){
return true;
}
//假设长度为1。则必须相等
if(end1 - start1 == 1 && end2 - start2 == 1){
return c1[start1] == c2[start2];
}
//长度不等返回false
if( end1 - start1 != end2 - start2){
return false;
}
int[] a = new int[128];
//每一个字符串的字符必须个数相等
for(int i = 0; i < end1 - start1; i++){
a[c1[i+start1]]++;
a[c2[i+start2]]--;
}
//不相等返回false
for(int i = 0; i < a.length; i++){
if(a[i] != 0){
return false;
}
}
//递归实现
for(int i = 1; i < end1 - start1; i++){
if(isScr(c1, c2, start1, start1+i, start2, start2+i) && isScr(c1, c2, start1+i, end1, start2+i, end2)){
return true;
}
if((isScr(c1, c2, start1, start1+i, end2-i, end2) && isScr(c1, c2, start1+i, end1, start2, end2-i))){
return true;
}
}
return false;
}
}