Leetcode 87 Scramble String

Leetcode 87 Scramble String

The problem description is as follow:

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.

Recursive Approach

Edit Scramble String on GitHub

The recursive approach is straight-forward. If string s1 is a scrambled string of string s2, then there must exists a point that breaks string s1 into two parts s11 and s12 and a point that breaks string s2 into two parts s21 and s22 where:

1. s11 is a scrambled string of s21, s12 is a scrambled string of s22. Or
2. s12 is a scrambled string of s21, s11 is a scrambled string of s22.

In order to make the recursive method more efficient, we can add some simple validation. If string s1 is a scrambled string of string s2, then they must share the same characters and have same length.

public class Solution {
    public boolean isScramble(String s1, String s2) {
        //Check lengths.
        if (s1.length() != s2.length())
            return false;
        if (s1.equals(s2))
            return true;
            
        int L = s1.length();
        //Check characters.
        int[] chars = new int[26];
        for (int i = 0; i < L; i++) {
            chars[s1.charAt(i) - 'a']++;
            chars[s2.charAt(i) - 'a']--;
        }
            
        for (int i = 0; i < 26; i++) {
            if (chars[i] != 0)
                return false;
        }
 
        //More letters
        for (int i = 1; i < L; i++) {
            String s11 = s1.substring(0, i);
            String s12 = s1.substring(i, L);
            String s21 = s2.substring(0, i);
            String s22 = s2.substring(i, L);
            if (isScramble(s11, s21) && isScramble(s12, s22))
                return true;
            s21 = s2.substring(0, L - i);
            s22 = s2.substring(L - i, L);
            if (isScramble(s11, s22) && isScramble(s12, s21))
                return true;
        }
        return false;
    }
}

Dynamice Programming Approach

Edit Scramble String on GitHub

Even if we add bunch of validations in the recursive approach, the time complexity is still not polynomial. In this case, we should seek a more efficient approach – DP approach.

I use a 3-D matrix scramble[][][] to save all the states. Say scramble[i][j][k], i stands for the starting index of string s1 and j stands for the starting index of string s2.  k stands for the length of current string. scramble[i][j][k] = true means s1.substring(i,i+k) and s1.substring(j,j+k) are scrambled strings.

Now we only have to figure how to get the recursive formula for scramble[i][j][k] from historical states we already got. As we discussed in the recursive approach,  if string s1 is a scrambled string of string s2, then there must exists a point that breaks string s1 into two parts s11 and s12 and a point that breaks string s2 into two parts s21 and s22 where:

1. s11 is a scrambled string of s21, s12 is a scrambled string of s22. Or
2. s12 is a scrambled string of s21, s11 is a scrambled string of s22.

Translating words into maths, we got:

For 1<=k<len,
scramble[i][j][len] |= (scramble[i][j][k]&&scramble[i+k][j+k][len-k] 
                       || scramble[i][j+len-k][k]&&scramble[i+k][j][len-k])

Here comes the code:

public class Solution {
    public boolean isScramble(String s1, String s2) {
        //Check lengths.
        if (s1==null || s2==null || s1.length() != s2.length())
            return false;
        if (s1.equals(s2))
            return true;
            
        int L = s1.length();
        // scramble[i][j][k]=true means: s1.substring(i,i+k) and s2.substring(j,j+k) is scramble
        // Thus scramble[i][j][0] has no meaning, k start from 1
        boolean[][][] scramble = new boolean[L][L][L+1];
        // Initiate scramble[][][], note that in Java boolean's default value is false
        for (int i = 0; i < L; i++) {
            for (int j = 0; j < L; j++)
                if (s1.charAt(i) == s2.charAt(j))
                    scramble[i][j][1] = true;
        }
        
        for (int len = 2; len <= L; len++) {
            for (int i = 0;i < L - len + 1; i++) {
                for(int j = 0; j < L - len + 1; j++) {
                    for(int k = 1; k < len; k++) {
                        scramble[i][j][len] |= (scramble[i][j][k]&&scramble[i+k][j+k][len-k] || scramble[i][j+len-k][k]&&scramble[i+k][j][len-k]);
                    }
                }
            }
        }
        return scramble[0][0][L];
    }
}

The time complexity is O(n^4) and space complexity is O(n^3), all polynomial.

Now we are happy 😀