【题目】
Given a strings1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation ofs1="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 stringss1ands2of the same length, determine ifs2is a scrambled string ofs1.
【解析】
题意：判断两个字符串是否能通过二叉树的左右子树交换相等。
【递归解法】
其实也是暴力遍历，把s1，s2分别分成两部分，判断s1的两部分和s2的两部分是否分别可以交换相等。
public class Solution {public boolean isScramble(String s1, String s2) {if (s1.length() != s2.length()) return false;if (s1.equals(s2)) return true;char[] c1 = s1.toCharArray();char[] c2 = s2.toCharArray();Arrays.sort(c1);Arrays.sort(c2);if (!Arrays.equals(c1, c2)) return false;for (int i = 1; i < s1.length(); i++) {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;}}
参考：https://leetcode.com/discuss/3632/any-better-solution
【动态规划解法】
这道题用二维数组来存储中间结果已经不行了，需要一个三维数组 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 class Solution {public boolean isScramble(String s1, String s2) {if (s1.length() != s2.length()) return false;if (s1.equals(s2)) return true;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(); 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()];}}
参考：
也就越容易失败，还不如怀揣一颗平常心，“但行好事，莫问前程”，往往成功的几率反而更大些
