[LeetCode] Scramble String

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.

[Solution].java

//should use dp to make it more efficient
public class Solution {
    public boolean isScramble(String s1, String s2) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        return isScramble(s1, s2, 0, s1.length(), 0, s2.length());
    }
    
    public boolean isScramble(String s1, String s2, int s1Begin, int s1End, int s2Begin, int s2End) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(s1End - s1Begin == 1 && s2End - s2Begin == 1 && s1.charAt(s1Begin) == s2.charAt(s2Begin)) return true;
        else if(s1End - s1Begin < 1 && s2End - s2Begin < 1) return false;
        else if(s1End > s1.length() || s2End > s2.length()) return false;
        boolean haveFind = false;
        for(int gap = 1; gap < s1End - s1Begin; gap++){
            if(similar(s1, s2, s1Begin, s1Begin + gap, s2Begin, s2Begin + gap)){
                haveFind = isScramble(s1, s2, s1Begin, s1Begin + gap, s2Begin, s2Begin + gap) &&
                	isScramble(s1, s2, s1Begin + gap, s1End, s2Begin + gap, s2End);
            	if(haveFind) return true;
            }
            else if(similar(s1, s2, s1Begin, s1Begin + gap, s2End - gap, s2End)){
                haveFind = isScramble(s1, s2, s1Begin, s1Begin + gap, s2End - gap, s2End) &&
        			isScramble(s1, s2, s1Begin + gap, s1End, s2Begin, s2End - gap);
        		if(haveFind) return true;
            }
        }
        return haveFind;
    }
    
    public boolean similar(String a, String b, int s1Begin, int s1End, int s2Begin, int s2End){
        int[] letters = new int[26];
        for(int i = s1Begin; i < s1End; i++){
            letters[a.charAt(i) - 'a']++;
        }
        for(int i = s2Begin; i < s2End; i++){
            letters[b.charAt(i) - 'a']--;
        }
        for(int i = 0; i < letters.length; i++){
            if(letters[i] != 0) return false;
        }
        return true;
    }
}