Scramble String

Q:
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.

A:
 首先，我们想到的是递归调用
代码如下：

public class Solution {
       public boolean isScramble(String s1, String s2) {
        // idea: assume s1 is original string , and s2 is the scrambled one
        // if scrambled, it must be that it is first k letters of s2 is the
        // scramble of first k letters of s1
        if(s1.length() != s2.length())
            return false;
        if(s1.length() == 1){
            return s1.charAt(0) == s2.charAt(0);
        }
        for(int i = 1;i< s1.length()-1; i++){ // i is the position , belongs to left part
            boolean left1 = isScramble(s1.substring(0,i+1),s2.substring(0,i+1));
            boolean right1 = isScramble(s1.substring(i+1),s2.substring(i+1));
            
            boolean left2 = isScramble(s1.substring(0,i+1),s2.substring(s2.length() - i));
            boolean right2 = isScramble(s1.substring(s1.length() - i),s2.substring(0,i+1));
            
            if(left1 && right1 || left2 && right2)
                return true;
        }
        return false;
       }
}

当然，结果是太慢 TLE


-----------下面是非递归的方法。  ------------------


主要错误在于： 对每个position， 我们有两个选择， 或者在这个点scramble或者在这里继续向两边分。

public class ScrambleString {
    public boolean isScramble(String s1, String s2) {
        // idea: assume s1 is original string , and s2 is the scrambled one
        // if scrambled, it must be that it is first k letters of s2 is the
        // scramble of first k letters of s1
        if (s1.length() != s2.length())
            return false;
        if (s1.length() == 1) { // s2.length == 1
            if (s1.equals(s2)) {
                return true;
            } else {
                return false;
            }
        }
        // NOW string length >= 1
        int n = s1.length();
        // for the first k letters, check it is the left scramble.
        if (s1.equals(s2)) {
            return true;
        }
        // find a split at split index i
        // At position i, we have two choice,
        // 1) permute here,
        // 2) continue split at i, left to left, right to right
        for (int i = 1; i < s1.length(); i++) {// left and right should not
                                                // be empty
            // CASE 1: we scramble at this position
            // if left of s1 == right of s2, they are the same, we can return
            // true
            String s1LeftI = s1.substring(0, i);
            String s1AfterI = s1.substring( i);
            // if left of s1 is the same with right of s2, and vice versa
            String s2MatchLeftS1 = s2.substring(n - i);
            String s2MatchRightS1 = s2.substring(0, n - i);
            if (isPermuation(s1LeftI, s2MatchLeftS1)&& isPermuation(s1AfterI, s2MatchRightS1)) {
                boolean left = isScramble(s1LeftI, s2MatchLeftS1);
                boolean right = isScramble(s1AfterI, s2MatchRightS1);
                if (left && right) {
                    return true;
                }
            }
            String s2LeftI = s2.substring(0, i);
            String s2AfterI = s2.substring( i);
            if (isPermuation(s1LeftI, s2LeftI)&& isPermuation(s1AfterI, s2AfterI)) {
                // if left of s1 is permuation of ( left of s2), and
                boolean left = isScramble(s1LeftI,
                        s2LeftI);
                boolean right = isScramble(s1AfterI, s2AfterI);
                if (left && right) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean isPermuation(String str1, String str2) {
        char[] a = str1.toCharArray();
        char[] b = str2.toCharArray();
        Arrays.sort(a);
        Arrays.sort(b);
        return Arrays.equals(a,b);
    }
}

Mistakes:
1: 光顾的左右分区了，没有考虑，交换过来的情况。
2: 自己的命名挺ugly的。呵呵

Learned:
1: java 中， Arrays.sort（）是基于int （或者double）类型的   quicksort实现。
因此，char [] 也可以直接调用，
--------------------------------第二遍-----------思想同上--------

public class Solution {
 public boolean isScramble(String s1, String s2) {
        // idea: assume s1 is original string , and s2 is the scrambled one
        // if scrambled, it must be that it is first k letters of s2 is the
        // scramble of first k letters of s1
        if (s1.length() != s2.length())
            return false;
        if (s1.length() == 1) {
            return s1.charAt(0) == s2.charAt(0);
        }
        char[] ch1 = s1.toCharArray();
        char[] ch2 = s2.toCharArray();
        Arrays.sort(ch1);
        Arrays.sort(ch2);
        // check whether ch1 == ch2
        if(Arrays.equals(ch1,ch2)==false)
            return false;
        // now, characters are the same, we check their scrambling
        for (int leftLen = 1; leftLen < s1.length(); leftLen++) { // i is the length of left
                                                    // part of s1
            String leftS1 = s1.substring(0, leftLen );
            String rightS1 = s1.substring(leftLen );
            // if left i part match s1
            String leftS2 = s2.substring(0, leftLen);
            String rightS2 = s2.substring(leftLen );

            if (isScramble(leftS1, leftS2) && isScramble(rightS1, rightS2))
                return true;

            // now test case 2, where s2 is scrambled to the right part
            String s2MatchLeftS1 = s2.substring(s2.length() - leftLen);
            String s2MatchRightS2 = s2.substring(0, s2.length() - leftLen);

            if (isScramble(leftS1, s2MatchLeftS1) && isScramble(rightS1, s2MatchRightS2))
                return true;
        }
        return false;
    }
}

------------------------------3 rd -----------------思路同第二遍----------------
Error:
1:      很傻比， 不知道，s1的左边要跟s2的右边比较，  反而去左边和左边比较，右边和右边比较去了。  哎，SB
2:     脑子被驴踢了，哎，竟然能犯这个SB 错误。  自己看看吧。 为什么下面这样写不对。

import java.util.Arrays;

public class Solution {
    public boolean isScramble(String s1, String s2) {
        // use recursive idea, but instead of trying every possible chars,
        if (s1.length() != s2.length())
            return false;
        int n = s1.length();
        if (n == 0 || s1.equals(s2))
            return true;
        // now beginning and end is not equal, we need do left right matching
        for (int i = 1; i < n; i++) {
            String s1Left = s1.substring(0, i);
            String s1Right = s1.substring(i);

            // test whether left of s1 equals left of s2
            String s2Left = s2.substring(0, i);
            String s2Right = s2.substring(i);
            if (isEqualAfterSort(s1Left, s2Left))
                return isScramble(s1Left, s2Left)
                        && isScramble(s1Right, s2Right);

            s2Left = s2.substring(0, n - i);
            s2Right = s2.substring(n - i);
            // if left of s1 equals to right of s2
            if (isEqualAfterSort(s1Left, s2Right))
                return isScramble(s1Left, s2Right)
                        && isScramble(s1Right, s2Left);
        }
        return false;
    }

    private boolean isEqualAfterSort(String str1, String str2) {
        char[] arr1 = str1.toCharArray();
        char[] arr2 = str2.toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        String ss1 = new String(arr1);
        String ss2 = new String(arr2);
        return ss1.equals(ss2);
    }
}

揭示错误2：  因为，即使两个sort后是一样的，但依然不能保证是scramble的。 因此，不能直接返回结果， 而应该是match之后，如果是true，才能返回