Question

link

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.

Stats

Frequency 2
Difficulty 5
Adjusted Difficulty 5
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is problem can be solved by either DFS or DP.

This blog have a very good analysis of the DFS approach.

Note that the binary tree can be constructed arbitrarily. So the general idea to tackle this problem is to enumerate every possible binary trees using DFS to see if two strings are scrambled strings. We can accelerate this process by adding a very efficient pruning.
Given two strings, s1, s2. First check if they have same letters and same length, denote as len.
For any l (1 <= l <= len): partition s1 into s11 = s1[0 : l), s12 = s1[l : len). We have two ways to partition s1:

  1. s21 = s2[0 : 1), s22 = s2[l : len). In this case, check s11 and s21 have same letters and are scrambled strings. And check s12 and s22 have same letters and are scrambled strings
  2. s21 = s2[0 : len – l), s22 = s2[len – l : len). In this case, check s11 and s22 have same letters and are scrambled strings. Then check s12 and s21 have same letters and are scrambled strings

This blog have a very good DP analysis.

dp[i][j][k] 代表了s1从i开始，s2从j开始，长度为k的两个substring是否为scramble string。
有三种情况需要考虑：
1. 如果两个substring相等的话，则为true
2. 如果两个substring中间某一个点，左边的substrings为scramble string， 同时右边的substrings也为scramble string，则为true
3. 如果两个substring中间某一个点，s1左边的substring和s2右边的substring为scramble string, 同时s1右边substring和s2左边的substring也为scramble string，则为true

For more explanation, this blog and this blog and this blog have discussed about it.

Code

my code

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

private boolean sameLetters(String a, String b) {
    if (a.length() != b.length()) return false;
    int[] count = new int[26];
    for (Character aa: a.toCharArray())
        count[aa - 'a'] ++;
    for (Character bb: b.toCharArray())
        if (count[bb - 'a'] -- <= 0)
            return false;
    return true;
}

Updated on July 5th, 2014: written again with less substring operations and more variables inside the method:

public boolean isScramble(String s1, String s2) {
    if (s1 == null || s2 == null || s1.length() != s2.length()) {
        return false;
    }
    int len = s1.length();
    return helper(s1, 0, len - 1, s2, 0, len - 1);
}

private boolean helper(String s1, int a1, int b1, String s2, int a2, int b2) {
    if (a1 - b1 != a2 - b2)
        return false;
    // check s1[a1, b1] and s2[a2, b2] have same set of letters
    int[] count = new int[26];
    for (int i = a1; i <= b1; i++)
        count[s1.charAt(i) - 'a'] ++;
    for (int i = a2; i <= b2; i++)
        if (count[s2.charAt(i) - 'a'] -- <= 0)
            return false;
    // check s1[a1, b1] and s2[a2, b2] is scramble or not
    if (a1 == b1) {
        return (s1.charAt(a1) == s2.charAt(a2));
    }
    for (int i = 0; i < b1 - a1; i++) {
        boolean check = helper(s1, a1, a1 + i, s2, a2, a2 + i)
                    && helper(s1, a1 + i + 1, b1, s2, a2 + i + 1, b2);
        if (check) return true;
        check = helper(s1, a1, a1 + i, s2, b2 - i, b2)
                    && helper(s1, a1 + i + 1, b1, s2, a2, b2 - i - 1);
        if (check) return true;
    }
    return false;
}

DP code, not written by me

public boolean isScramble(String s1, String s2) {
    int n = s1.length();
    boolean[][][] dp = new boolean[n][n][n + 1];
    for (int i = n - 1; i >= 0; i--)
        for (int j = n - 1; j >= 0; j--)
            for (int k = 1; k <= n - Math.max(i, j); k++) {
                if (s1.substring(i, i + k).equals(s2.substring(j, j + k)))
                    dp[i][j][k] = true;
                else {
                    for (int l = 1; l < k; l++) {
                        if (dp[i][j][l] && dp[i + l][j + l][k - l]
                            || dp[i][j + k - l][l] && dp[i + l][j][k - l]) {
                            dp[i][j][k] = true;
                            break;
                        }
                    }
                }
            }
    return dp[0][0][n];
}