Scramble String

Problem

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

Recursive Solution: O(4 ^ n) time

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) return true;
        if (s1.length() != s2.length()) return false;
        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 count : letters) if (count != 0) return false;

        for (int i = 1; i < s1.length(); i++) {
            String s1Left = s1.substring(0, i), s2Left = s2.substring(0, i);
            String s1Right = s1.substring(i), s2Right = s2.substring(i);
            if (isScramble(s1Left, s2Left) && isScramble(s1Right, s2Right)) return true;
            //Swap case:
            String s2LeftSwap = s2.substring(s2.length() - i);
            String s2RightSwap = s2.substring(0, s2.length() - i);
            if (isScramble(s1Left, s2LeftSwap) && isScramble(s1Right, s2RightSwap)) return true; 
        }

        return false;
    }
}

Analysis

We use recursive to check each possibles
We first check directly equal() and then frequency of each letter
Then we check every possible substrings by a loop from i = 1 till end
If corresponding left and right substrings of i have not returned, we reach the swap case
Which is we need to compare s1Left with s2LeftSwap and s1Right with s2RightSwap
Notice that time complexity is exponential because we divide the whole problem into 4 sub problems