Scramble String | Leetcode

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: Iterate through the string and split each string into two parts. The first part consists of the first i characters of S1, and the second part the rest of S1. Try to match this with two parts from S2.

The first way to split S2 into two parts is to take the first i characters of S2, and then the rest of S2.

The second way to split S2 into two parts is to take the last (length - i) characters of S2, and then the first (length - i) characters of S2.

The code "if (s1.chars().sum() != s2.chars().sum()) return false;" is to check that if the characters in S1 and S2 are different, then they cannot be scrambles of each other. This line is needed only to improve the speed of the algorithm to beat leetcode's online judge. The check is not foolproof, but it is good enough to pass leetcode's test.

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) return true;
        if (s1.chars().sum() != s2.chars().sum()) return false;
        
        for (int i = 1; i < s1.length(); i++) {
            String left1 = s1.substring(0, i);
            String right1 = s1.substring(i);
            
            String left2 = s2.substring(0, i);
            String right2 = s2.substring(i);
            
            if (isScramble(left1, left2) && isScramble(right1, right2)) {
                return true;
            }
            
            int j = s2.length() - i;
            right2 = s2.substring(j);
            left2 = s2.substring(0, j);
            
            if (isScramble(left1, right2) && isScramble(right1, left2)) {
                return true;
            }
        }
        
        return false;
    }
}