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.

https://oj.leetcode.com/problems/scramble-string/

思路1：枚举DFS，比如要比较s1和s2，s1分成a1和b1，s2分成a2和b2，需要分别比较((a1~a2) && (b1~b2)）或者 （(a1~b2) && (a1~b2))。

思路2：DP。dp[i][j][k]表示s1从i开始k长度的字符串与s2从从j开始k长度的字符串是否是scrambled string。

当k=1时，只需比较s1.charAt(i)是否等于s2.charAt(j)即可。

当k>1是，需要枚举分割点，令左半边长度为l，则右边长度为k-l，（1<l<k）。对于每个l，比较((a1~a2) && (b1~b2)）或者 （(a1~b2) && (a1~b2))。

public class Solution {    public boolean isScramble(String s1, String s2) {        if (s1.length() != s2.length())            return false;        int len = s1.length();        boolean dp[][][] = new boolean[len][len][len + 1];        for (int k = 1; k <= len; k++) {            for (int i = 0; i <= len - k; i++) {                for (int j = 0; j <= len - k; j++) {                    if (k == 1)                        dp[i][j][k] = (s1.charAt(i) == s2.charAt(j));                    else {                        for (int l = 1; l < k; l++) {                            if (dp[i][j][l] && dp[i + l][j + l][k - l] || dp[i][j + k - l][l] && dp[i + l][j][k - l]) {                                dp[i][j][k] = true;                                break;                            }                        }                    }                }            }        }        return dp[0][0][len];    }    public static void main(String[] args) {        System.out.println(new Solution().isScramble("great", "rgeat"));        System.out.println(new Solution().isScramble("great", "rgtae"));        System.out.println(new Solution().isScramble("great", "rgtta"));    }}

View Code

参考：

http://blog.csdn.net/pickless/article/details/11501443

http://www.blogjava.net/sandy/archive/2013/05/22/399605.html