[LeetCode] 87. Scramble String

Posted on | In

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":

1
2
3
4
5
6
7
    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".

1
2
3
4
5
6
7
    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".

1
2
3
4
5
6
7
    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.

Example 1:

1
2
Input: s1 = "great", s2 = "rgeat"
Output: true

Example 2:

1
2
Input: s1 = "abcde", s2 = "caebd"
Output: false

Explanation

  1. We can use recusive method to solve this problem. For example, when string1 is “rgeat”, string2 is “great”. First, we need to loop to check every possibility of splitting of string1, we can split string1 as “r|geat”, “rg|eat”, “rge|eat”, etc. In each splitting, we check string1’s left side is scramble of string2’s left side and string1’s right side is scramble of string2’s right side.

  2. For example, when string1’s splitting is “rg|eat”, its left side is “rg”, right side is “eat”. We compare “rg” with the same length of string2’s left side, which is “gr”, and we compare string1’s right side “eat” with string2’s same length right side, which is “eat”. In other word, we recursivly check “rg” with “gr” is scramble, and compare “eat” with “eat” is scramble. If string1’s left side and string2’left side is scramble and also string1’s right side and stirng2’s right side is scramble, then string1 and string2 is scramble.

  3. Similarlly, string1 and string2 can also be scramble if this condition: string1’s left side and string2’s right side is scramble and also string1’s right side and string2’s left side is scramble. For example, string1 is “rg”, string2 is “gr”, string1’s left side “r” matches string2’s right side “r”, and also string1’s right side “g” matches string2’s left side “g”, so “rg” and “gr” is scramble.

  4. The base case is when string1 and string2 have length 1 and they are equal, then both string are scramble.

  5. We can improve the performance by sorting the string and compare, if they are not equal, immediatly return false.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1 == null || s2 == null || s1.length() != s2.length()) return false;
        if (s1.length() == 1 && s1.equals(s2)) return true;

        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        String sortStr1 = new String(arr1);
        String sortStr2 = new String(arr2);
        if (!sortStr1.equals(sortStr2)) return false;

        int s1Len = s1.length();
        int s2Len = s2.length();

        for (int i = 1; i < s1.length(); i++) {
            String s1Left = s1.substring(0, i);
            String s1Right = s1.substring(i, s1Len);
            if (isScramble(s1Left, s2.substring(0, i)) && isScramble(s1Right, s2.substring(i))
                    || isScramble(s1Left, s2.substring(s2Len-i))
                        && isScramble(s1Right, s2.substring(0, s2Len-i))) {
                return true;
            }
        }
        return false;
    }
}