LeetCode 87 - Scramble String

Scramble String - 小明思考 - BlogJava

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.

这个问题是google的面试题。由于一个字符串有很多种二叉表示法，貌似很难判断两个字符串是否可以做这样的变换。
对付复杂问题的方法是从简单的特例来思考，从而找出规律。
先考察简单情况：
字符串长度为1：很明显，两个字符串必须完全相同才可以。
字符串长度为2：当s1="ab", s2只有"ab"或者"ba"才可以。
对于任意长度的字符串，我们可以把字符串s1分为a1,b1两个部分，s2分为a2,b2两个部分，满足（(a1~a2) && (b1~b2)）或者 （(a1~b2) && (a1~b2)）
解法二（动态规划）
这里我使用了一个三维数组boolean result[len][len][len],其中第一维为子串的长度，第二维为s1的起始索引，第三维为s2的起始索引。
result[k][i][j]表示s1[i...i+k]是否可以由s2[j...j+k]变化得来。
https://leetcode.com/problems/scramble-string/discuss/29396/Simple-iterative-DP-Java-solution-with-explanation
The iterative version of the idea is considerably slower than the recursive simply because here we consider all possible states, while the recursive will only compute required states as it founds them. Time complexity of both is, in any case, the same.

 public boolean isScramble(String s1, String s2) {
  if (s1.length() != s2.length()) return false;
  int len = s1.length();
  /**
   * Let F(i, j, k) = whether the substring S1[i..i + k - 1] is a scramble of S2[j..j + k - 1] or not
   * Since each of these substrings is a potential node in the tree, we need to check for all possible cuts.
   * Let q be the length of a cut (hence, q < k), then we are in the following situation:
   * 
   * S1 [   x1    |         x2         ]
   *    i         i + q                i + k - 1
   * 
   * here we have two possibilities:
   *      
   * S2 [   y1    |         y2         ]
   *    j         j + q                j + k - 1
   *    
   * or 
   * 
   * S2 [       y1        |     y2     ]
   *    j                 j + k - q    j + k - 1
   * 
   * which in terms of F means:
   * 
   * F(i, j, k) = for some 1 <= q < k we have:
   *  (F(i, j, q) AND F(i + q, j + q, k - q)) OR (F(i, j + k - q, q) AND F(i + q, j, k - q))
   *  
   * Base case is k = 1, where we simply need to check for S1[i] and S2[j] to be equal 
   * */
  boolean [][][] F = new boolean[len][len][len + 1];
  for (int k = 1; k <= len; ++k)
   for (int i = 0; i + k <= len; ++i)
    for (int j = 0; j + k <= len; ++j)
     if (k == 1)
      F[i][j][k] = s1.charAt(i) == s2.charAt(j);
     else for (int q = 1; q < k && !F[i][j][k]; ++q) {
      F[i][j][k] = (F[i][j][q] && F[i + q][j + q][k - q]) || (F[i][j + k - q][q] && F[i + q][j][k - q]);
     }
  return F[0][0][len];
 }

https://blog.csdn.net/yanglingwell/article/details/79536438
令 dp[i][j][size] 表示 s2.substr(j, size) 是否是 s1.substr(i, size) 的 scrambled string;
如果 size = 0, 则 s2 一定是 s1 的 scrambled string。即: dp[i][j][0] = true;
如果 size = 1, 则当 s1[i](s1.substr(i, 1)) 等于 s2[j](s2.substr(j, 1)) 时， s2 才是 s1 的 scrambled string;
否则, 若以下一条成立，则s2 一定是 s1 的 scrambled string：
s1 可能被拆分成 s1.substr(i, size-k) 和 s1.substr(i+size-k, k) 两段(两个子树), 然后交换位置形成 s2.substr(j, size)(如图)。 那么: dp[i][j][size] = (dp[i][j+k][size-k] && dp[i+size-k][j][k]);

s1 可能被拆分成 s1.substr(i, k) 和 s1.substr(i+k, size-k) 两段(两个子树), 然后分别对两段(两棵子树)进行可能的操作(如图)。 那么: dp[i][j][size] = (dp[i][j][k] && dp[i+k][j+k][size-k]);

https://discuss.leetcode.com/topic/23691/java-fast-dp-iteration-solution-and-recursion-solution
http://www.lifeincode.net/programming/leetcode-scramble-string-java/
https://discuss.leetcode.com/topic/36715/simple-iterative-dp-java-solution-with-explanation

 I use a three dimension array scramble[][][] to save the states. What scramble[k][i][j] means is that two substrings of length k, one starts from i of string s1, another one starts from j of string s2, are scramble. We are trying to find scramble[L][0][0]. For every length k, we try to divide the string to two parts differently, checking if there is a way that can make it true.

The complexity of DP version is O(n4)

    public boolean isScramble(String s1, String s2) {

        //Check lengths.

        if (s1.length() != s2.length())

            return false;

        if (s1.equals(s2))

            return true;

            

        int L = s1.length();

        boolean[][][] scramble = new boolean[L][L][L];

        for (int i = 0; i < L; i++) {

            for (int j = 0; j < L; j++)

                if (s1.charAt(i) == s2.charAt(j))

                    scramble[0][i][j] = true;

        }

        

        for (int k = 2; k <= L; k++) {

            for (int i = L - k; i >= 0; i--) {

                for (int j = L - k; j >= 0; j--) {

                    boolean canScramble = false;

                    for (int m = 1; m < k; m++) {

                        canScramble = (scramble[m - 1][i][j] && scramble[k - m - 1][i + m][j + m])

|| (scramble[m - 1][i][j + k -m] && scramble[k - m - 1][i + m][j]);

                        if (canScramble)

                            break;

                    }

                    scramble[k - 1][i][j] = canScramble;

                }

            }

        }

        

        return scramble[L - 1][0][0];

    }

   public boolean isScramble(String s1, String s2) {
        int len = s1.length();
        if(len!=s2.length()){
            return false;
        }
        if(len==0){
            return true;
        }
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        
        boolean[][][] result = new boolean[len][len][len];
        for(int i=0;i<len;++i){
            for(int j=0;j<len;++j){
                result[0][i][j] = (c1[i]==c2[j]);
            }
        }
        
        for(int k=2;k<=len;++k){
            for(int i=len-k;i>=0;--i){
              for(int j=len-k;j>=0;--j){
                  boolean r = false;
                  for(int m=1;m<k && !r;++m){
                      r = (result[m-1][i][j] && result[k-m-1][i+m][j+m]) || (result[m-1][i][j+k-m] && result[k-m-1][i+m][j]);
                  }
                  result[k-1][i][j] = r;
              }
            }
        }
        return result[len-1][0][0];
    }
http://n00tc0d3r.blogspot.com/2013/05/scramble-string.html
In the recursion solution, we split the strings and compare recursively. It ends up with comparing every possible pair of equal-length substrings in the two strings. So, suppose the length of the two strings is n, the subproblems are

• For each pair of (n-1)-char-long substrings of the two strings, are they scramble to each other?
• For each pair of (n-2)-char-long substrings, are they scramble?
• ... ...
• For each pair of 2-char-long substrings, are they scramble?
• For each pair of char in the two strings, are they scramble (i.e. do they equal)?

That is saying, we can build up a table and solve the problem in a bottom-up fashion.

Then to verify whether two k-char-long strings are scramble, we still split the two strings at k-1 position. For each pair of split, we don't need to take O(n) time to recursively compare the two of them. Instead, simply take O(1) time to look at the table.

public boolean isScramble(String s1, String s2) {  
   int len = s1.length();  
   if (len != s2.length()) return false;  
   if (s1.equals(s2)) return true;  
   
   // a table of matches  
   // T[i][j][k] = true iff s2.substring(j,j+k+1) is a scambled string of s1.substring(i,i+k+1)  
   boolean[][][] scrambled = new boolean[len][len][len];  
   for (int i=0; i < len; ++i) {  
     for (int j=0; j < len; ++j) {  
       scrambled[i][j][0] = (s1.charAt(i) == s2.charAt(j)); // here use 0 not 1 
     }  
   }  
   
   // dynamically fill up the table  
   for (int k=1; k < len; ++k) { // k: length  
     for (int i=0; i < len - k; ++i) { // i: index in s1  
       for (int j=0; j < len - k; ++j) { // j: index in s2  
         scrambled[i][j][k] = false;  
         for (int p=0; p < k; ++p) { // p: split into [0..p] and [p+1..k]  
           if ((scrambled[i][j][p] && scrambled[i+p+1][j+p+1][k-p-1])  
               || (scrambled[i][j+k-p][p] && scrambled[i+p+1][j][k-p-1])) {  
             scrambled[i][j][k] = true;  
             break;  
           }  
         }  
       }  
     }  
   }  
   
   return scrambled[0][0][len-1];  
 }  

http://www.acmerblog.com/leetcode-solution-scramble-string-6224.html

05	bool isScramble(string s1, string s2) {

06	const int N = s1.size();

07	if (N != s2.size()) return false;

08

09	// f[n][i][j]，表示长度为n，起点为s1[i]和

10	// 起点为s2[j]两个字符串是否互为scramble

11	bool f[N + 1][N][N];

12	fill_n(&f[0][0][0], (N + 1) * N * N, false);

13

14	for (int i = 0; i < N; i++)

15	for (int j = 0; j < N; j++)

16	f[1][i][j] = s1[i] == s2[j];

17

18	for (int n = 1; n <= N; ++n) {

19	for (int i = 0; i + n <= N; ++i) {

20	for (int j = 0; j + n <= N; ++j) {

21	for (int k = 1; k < n; ++k) {

22	if ((f[k][i][j] && f[n - k][i + k][j + k]) ||

23	(f[k][i][j + n - k] && f[n - k][i + k][j])) {

24	f[n][i][j] = true;

25

break;

26

}

27

}

28

}

29

}

30

}

31	return f[N][0][0];

32

}

16	// 剪枝，提前返回

17	int A[26]; // 每个字符的计数器

18	fill(A, A + 26, 0);

19	for(int i = 0; i < length; i++) A[*(first1+i)-'a']++;

20	for(int i = 0; i < length; i++) A[*(first2+i)-'a']--;

21	for(int i = 0; i < 26; i++) if (A[i] != 0) return false;

http://blog.csdn.net/linhuanmars/article/details/24506703
这道题看起来是比较复杂的，如果用brute force，每次做切割，然后递归求解，是一个非多项式的复杂度，一般来说这不是面试官想要的答案。
这其实是一道三维动态规划的题目，我们提出维护量res[i][j][n]，其中i是s1的起始字符，j是s2的起始字符，而n是当前的字符串长度，res[i][j][len]表示的是以i和j分别为s1和s2起点的长度为len的字符串是不是互为scramble。
有了维护量我们接下来看看递推式，也就是怎么根据历史信息来得到res[i][j][len]。判断这个是不是满足，其实我们首先是把当前s1[i...i+len-1]字符串劈一刀分成两部分，然后分两种情况：第一种是左边和s2[j...j+len-1]左边部分是不是scramble，以及右边和s2[j...j+len-1]右边部分是不是scramble；第二种情况是左边和s2[j...j+len-1]右边部分是不是scramble，以及右边和s2[j...j+len-1]左边部分是不是scramble。如果以上两种情况有一种成立，说明s1[i...i+len-1]和s2[j...j+len-1]是scramble的。而对于判断这些左右部分是不是scramble我们是有历史信息的，因为长度小于n的所有情况我们都在前面求解过了（也就是长度是最外层循环）。
上面说的是劈一刀的情况，对于s1[i...i+len-1]我们有len-1种劈法，在这些劈法中只要有一种成立，那么两个串就是scramble的。
总结起来递推式是res[i][j][len] = || (res[i][j][k]&&res[i+k][j+k][len-k] || res[i][j+len-k][k]&&res[i+k][j][len-k]) 对于所有1<=k<len，也就是对于所有len-1种劈法的结果求或运算。因为信息都是计算过的，对于每种劈法只需要常量操作即可完成，因此求解递推式是需要O(len)（因为len-1种劈法）。
如此总时间复杂度因为是三维动态规划，需要三层循环，加上每一步需要线行时间求解递推式，所以是O(n^4)。虽然已经比较高了，但是至少不是指数量级的，动态规划还是有很大有事的，空间复杂度是O(n^3)。代码如下：

public boolean isScramble(String s1, String s2) {
    if(s1==null || s2==null || s1.length()!=s2.length())
        return false;
    if(s1.length()==0)
        return true;
    boolean[][][] res = 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++)
        {
            res[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++)
                {
                    res[i][j][len] |= res[i][j][k]&&res[i+k][j+k][len-k] || res[i][j+len-k][k]&&res[i+k][j][len-k];
                }
            }
        }
    }
    return res[0][0][s1.length()];
}

http://www.jiuzhang.com/solutions/scramble-string/
X. Recursion + Memorization
https://leetcode.com/problems/scramble-string/discuss/29392/Share-my-4ms-c%2B%2B-recursive-solution
https://leetcode.com/problems/scramble-string/discuss/29387/Accepted-Java-solution
I think the complexity of this algorithm is O(n*(3^n));
proof:
T(n) = 2*(T(1)+T(2)+....T(n-1))+O(n) this means T(n)/n<2*((T(1)/1)+(T(2)/2)+(T(3)/3)+....T(n-1)/(n-1))
then T(n)/n<3T(n-1)/(n-1);So T(n)/n = O(3^n), T(n) = O(n(3^n))

    bool isScramble(string s1, string s2) {
        if(s1==s2)
            return true;
            
        int len = s1.length();
        int count[26] = {0};
        for(int i=0; i<len; i++)
        {
            count[s1[i]-'a']++;
            count[s2[i]-'a']--;
        }
        
        for(int i=0; i<26; i++)
        {
            if(count[i]!=0)
                return false;
        }
        
        for(int i=1; i<=len-1; i++)
        {
            if( isScramble(s1.substr(0,i), s2.substr(0,i)) && isScramble(s1.substr(i), s2.substr(i)))
                return true;
            if( isScramble(s1.substr(0,i), s2.substr(len-i)) && isScramble(s1.substr(i), s2.substr(0,len-i)))
                return true;
        }
        return false;
    }

Recursion + Memoization Solution implemented by nested hashmap, which can extend to all characters.

HashMap<String,HashMap<String,Boolean>> map = new HashMap<>();                //nested hashmap to implement memoization
    public boolean isScramble(String s1, String s2) {
        if(map.containsKey(s1) && map.get(s1).containsKey(s2)) return map.get(s1).get(s2);
        if(s1.length() == 1 && s2.length() == 1) return s1.equals(s2);
        for(int i = 0;i<s1.length()-1;i++){
            if(
                (isScramble(s1.substring(0,i+1),s2.substring(s2.length()-i-1))    //1) s1 left vs s2 right
               && isScramble(s1.substring(i+1),s2.substring(0,s2.length()-i-1)))  //&& s1 right vs s2 left
                || (isScramble(s1.substring(0,i+1),s2.substring(0,i+1))           //2) s1 left vs s2 left
               && isScramble(s1.substring(i+1),s2.substring(i+1)))                //&& s1 right vs s2 right
            ) {
                HashMap<String,Boolean> temp = map.getOrDefault(s1,new HashMap<>());
                temp.put(s2,true);
                map.put(s1,temp);
                return true;
            }
        }
        HashMap<String,Boolean> temp = map.getOrDefault(s1,new HashMap<>());
        temp.put(s2,false);
        map.put(s1,temp);
        return false;
    }

     private boolean checkScramble(String s1,int start1, String s2, int start2, int k, int [][][]visit) {
  if(visit[start1][start2][k] == 1)
            return true;
        if(visit[start1][start2][k] ==-1)
            return false;
        
        
        if (s1.length() != s2.length()) {
            visit[start1][start2][k] = -1;
            return false;
        }
        
        if (s1.length() == 0 || s1.equals(s2)) {
            visit[start1][start2][k] = 1;
            return true;
        }
        
        if (!isValid(s1, s2)) {
            visit[start1][start2][k] = -1;
            return false;
        }// Base Cases
        
        
        for (int i = 1; i < s1.length(); i++) {
            String s11 = s1.substring(0, i);
            String s12 = s1.substring(i, s1.length());
            
            String s21 = s2.substring(0, i);
            String s22 = s2.substring(i, s2.length());
            
            String s23 = s2.substring(0, s2.length() - i);
            String s24 = s2.substring(s2.length() - i, s2.length());
            
            if (checkScramble(s11,start1, s21, start2, i, visit) && checkScramble(s12, start1+i, s22, start2+i,k-i, visit))  {
                visit[start1][start2][k] = 1;
                return true;
            }
            
            if (checkScramble(s11,start1, s24, start2+k-i, i, visit) && checkScramble(s12,start1+i, s23,start2, k-i, visit))
            {
                visit[start1][start2][k] = 1;
                return true;
            }
        }
        visit[start1][start2][k] = -1;
        return false;
    }
    public boolean isScramble(String s1, String s2) {
        int len = s1.length();
        int [][][] visit = new int[len][len][len + 1];
        return checkScramble(s1,0,s2,0, len, visit);
    }
    
    
    private boolean isValid(String s1, String s2) {
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        if (!(new String(arr1)).equals(new String(arr2))) {
            return false;
        }
        return true;
    }

XP. Recursive Version（递归）时间复杂度是O(3n)?
https://discuss.leetcode.com/topic/23691/java-fast-dp-iteration-solution-and-recursion-solution/

Recursive version: with some pruning check at the beginning, finally get rid of TLE...

    public boolean isScramble(String s1, String s2) {
        int len= s1.length();
        if(s2.length()!=len) return false;
        if(s1.equals(s2)) return true;
        Map<Character,Integer> checkPermutation = new HashMap<Character,Integer>();
        for(int i = 0; i < len; i++) {
            char a = s1.charAt(i), b = s2.charAt(i);
            if(checkPermutation.containsKey(a)) checkPermutation.put(a,checkPermutation.get(a)+1);
            else checkPermutation.put(a,1);
            if(checkPermutation.containsKey(b)) checkPermutation.put(b,checkPermutation.get(b)-1);
            else checkPermutation.put(b,-1);
        }
        for(char c : checkPermutation.keySet()) if(checkPermutation.get(c)!=0) return false;
        
        for(int i = 1; i < s1.length(); i++) {
            if(isScramble(s1.substring(0,i),s2.substring(0,i))&&isScramble(s1.substring(i,len),s2.substring(i,len))) return true;
            else if(isScramble(s1.substring(0,i),s2.substring(len-i,len))&&isScramble(s1.substring(i,len),s2.substring(0,len-i))) return true;
        }
        return false;
    }

https://discuss.leetcode.com/topic/19158/accepted-java-solution
We can build global letters[][].

This is exponential complexity, something like O(3^n).

exponential complexity O(2^n)

    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) return true; 
        
        int[] letters = new int[26];
        for (int i=0; i<s1.length(); i++) {
            letters[s1.charAt(i)-'a']++;
            letters[s2.charAt(i)-'a']--;
        }
        for (int i=0; i<26; i++) if (letters[i]!=0) 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;
    }

两个字符串的相似的必备条件是含有相同的字符集。简单的做法是把两个字符串的字符排序后，然后比较是否相同。
加上这个检查就可以大大的减少递归次数。
Also http://www.lifeincode.net/programming/leetcode-scramble-string-java/
http://leetcodesolutionandsummaries.blogspot.com/2015/01/scramble-string.html
https://leetcode.com/discuss/46803/accepted-java-solution

If string s1 and s2 are scramble strings, there must be a point that breaks s1 to two parts s11, s12, and a point that breaks s2 to two parts, s21, s22, and isScramble(s11, s21) && isScramble(s12, s22) is true, or isScramble(s11, s22) && isScramble(s12, s21) is true.

So we can make it recursively. We just break s1 at different position to check if there exists one position satisfies the requirement.

Some checks are needed otherwise it will time out. For example, if the lengths of two strings are different, they can’t be scramble. And if the characters in two strings are different, they can’t be scramble either.

    public boolean isScramble(String s1, String s2) {

        //Check lengths.

        if (s1.length() != s2.length())

            return false;

        if (s1.equals(s2))

            return true;

            

        int L = s1.length();

        //Check characters.

        int[] chars = new int[26];

        for (int i = 0; i < L; i++) {

            chars[s1.charAt(i) - 'a']++;

            chars[s2.charAt(i) - 'a']--;

        }

            

        for (int i = 0; i < 26; i++) {

            if (chars[i] != 0)

                return false;

        }

        //More letters

        for (int i = 1; i < L; i++) {

            String s11 = s1.substring(0, i);

            String s12 = s1.substring(i, L);

            String s21 = s2.substring(0, i);

            String s22 = s2.substring(i, L);

            if (isScramble(s11, s21) && isScramble(s12, s22))

                return true;

            s21 = s2.substring(0, L - i);

            s22 = s2.substring(L - i, L);

            if (isScramble(s11, s22) && isScramble(s12, s21))

                return true;

        }

        return false;

    }

public boolean isScramble(String s1, String s2) {
        int l1 = s1.length();
        int l2 = s2.length();
        if(l1!=l2){
            return false;
        }
        if(l1==0){
            return true;
        }
        
        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        if(l1==1){
            return c1[0]==c2[0];
        }
        Arrays.sort(c1);
        Arrays.sort(c2);
        for(int i=0;i<l1;++i){
            if(c1[i]!=c2[i]){
                return false;
            }
        }
        
        boolean result = false;
        for(int i=1;i<l1 && !result;++i){
            String s11 = s1.substring(0,i);
            String s12 = s1.substring(i);
            String s21 = s2.substring(0,i);
            String s22 = s2.substring(i);
            result = isScramble(s11,s21) && isScramble(s12,s22);
            if(!result){
                String s31 = s2.substring(0,l1-i);
                String s32 = s2.substring(l1-i);
                result = isScramble(s11,s32) && isScramble(s12,s31);
            }
        }
        
        return result;
    }
https://leetcode.com/discuss/56746/java-fast-dp-iteration-solution-and-recursion-solution
public boolean isScramble(String s1, String s2) { int len= s1.length(); if(s2.length()!=len) return false; if(s1.equals(s2)) return true; Map<Character,Integer> checkPermutation = new HashMap<Character,Integer>(); for(int i = 0; i < len; i++) { char a = s1.charAt(i), b = s2.charAt(i); if(checkPermutation.containsKey(a)) checkPermutation.put(a,checkPermutation.get(a)+1); else checkPermutation.put(a,1); if(checkPermutation.containsKey(b)) checkPermutation.put(b,checkPermutation.get(b)-1); else checkPermutation.put(b,-1); } for(char c : checkPermutation.keySet()) if(checkPermutation.get(c)!=0) return false; for(int i = 1; i < s1.length(); i++) { if(isScramble(s1.substring(0,i),s2.substring(0,i))&&
isScramble(s1.substring(i,len),s2.substring(i,len))) return true; else if(isScramble(s1.substring(0,i),s2.substring(len-i,len))
&&isScramble(s1.substring(i,len),s2.substring(0,len-i))) return true; } return false; }
http://n00tc0d3r.blogspot.com/2013/05/scramble-string.html
Given two strings, try every possible split of s1 and check whether the resulted substrings of s1 equal or "swap-equal" of the corresponding substrings of s2.

For example, given "great" and "rgate", the splits are

• ("great") vs. ("rgate")
• ("g", "reat") vs. ("r", "gate") or ("rgat", "e")
• ("gr", "eat") vs. ("rg", "ate") or ("te", "rga")
• ("gre", "at") vs. ("rga", "te") or ("ate", "rg")
• ("grea", "t") vs. ("rgat", "e") or ("gate", "r")

 public boolean isScramble(String s1, String s2) {  
   int len = s1.length();  
   if (len != s2.length()) return false;  
   if (s1.equals(s2)) return true;  
   
   for (int i=1; i < len; ++i) {  
     String s1l = s1.substring(0, i), s1r = s1.substring(i, len);  
     // w/o swap  
     String s2l = s2.substring(0, i), s2r = s2.substring(i, len);  
     if (isScramble(s1l, s2l) && isScramble(s1r, s2r)) return true;  
     // w/ swap  
     s2l = s2.substring(0, len-i); s2r = s2.substring(len-i, len);  
     if (isScramble(s1l, s2r) && isScramble(s1r, s2l)) return true;  
   }  
   
   return false;  
 }  

There are O(n) possible split points. At each point, there are two possibilities: with swap and without swap. At each point, we recursively check the two substrings until both of them are single character, which takes time O(2^k+2^(n-k)), where k and n-k are the lengths of the two substrings. So, this algorithm runs in exponential time, O(2^n), and space complexity is also exponential (recursion stack).

With Cache -- the map did not cache false case.

 private boolean isScrambleHelper(String s1, String s2, HashMap<String, String> map) {  
   int len = s1.length();  
   if (len != s2.length()) return false;  
   if (s1.equals(s2) || s2.equals(map.get(s1))) return true;  
   
   for (int i=1; i < len; ++i) {  
     String s1l = s1.substring(0, i), s1r = s1.substring(i, len);  
     // w/o swap  
     String s2l = s2.substring(0, i), s2r = s2.substring(i, len);  
     if (isScramble(s1l, s2l) && isScramble(s1r, s2r)) {  
       map.put(s1l, s2l); map.put(s1r, s2r);  
       return true;  
     }  
     // w/ swap  
     s2l = s2.substring(0, len-i); s2r = s2.substring(len-i, len);  
     if (isScramble(s1l, s2r) && isScramble(s1r, s2l)) {  
       map.put(s1l, s2r); map.put(s1r, s2l);  
       return true;  
     }  
   }  
   
   return false;  
 }  
   
 public boolean isScramble(String s1, String s2) {  
   return isScrambleHelper(s1, s2, new HashMap<String, String>());  
 }  




https://leetcode.com/discuss/2504/can-you-partition-string-index-any-time-producing-scramble

For instance, ABCDE. There exists no scramble like CAEBD under the given operations.

http://yihuad.blogspot.com/2013/10/scramble-string-leetcode.html
Read full article from Scramble String - 小明思考 - BlogJava