Description

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.

Example 1:

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

Example 2:

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

Solutions

N=len(s1)=len(s2)

isScramble(s1, s2) iff s1s2可以分为两部分,这两部分分别符合Scramble String。

即存在0<k<N,使得isScramble(s1[:k], s2[:k]) && isScramble(s1[k:], s2[k:])或者isScramble(s1[:k], s2[N-k:]) && isScramble(s1[k:], s2[:N-k])

对应下面两种匹配方式:

下面是两种解法:

Top-down

这里使用了prefixSum和suffixSum来进行剪枝

  • 如果check(s1[:k], s2[:k])则s1[:k], s2[:k]的和一定相等,所以先判断prefixSum1和prefixSum2
  • 如果check(s1[:k], s2[N-k:])则s1[:k], s2[N-k:]的和一定相等,所以先判断prefixSum1和suffixSum2

Python:

class Solution:
    def isScramble(self, s1, s2):
        if len(s1)!=len(s2): return False
        def check(S1, S2):
            if S1==S2: return True
            if sorted(S1)!=sorted(S2): return False
            N = len(S1)
            prefixSum1 = 0
            prefixSum2, suffixSum2 = 0, 0
            for i in range(N):
                if i>0 and prefixSum1==prefixSum2 and check(S1[:i], S2[:i]) and check(S1[i:], S2[i:]): return True
                if i>0 and prefixSum1==suffixSum2 and check(S1[:i], S2[N-i:]) and check(S1[i:], S2[:N-i]): return True
            return False
        return check(s1, s2)

Java:

class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.length()!=s2.length()) {
            return false;
        }
        if (s1.equals(s2)) {
            return true;
        }
        int counter1[] = new int[26], counter2[]=new int[26];
        for (char c:s1.toCharArray()) {
            counter1[c-'a']++;
        }
        for (char c:s2.toCharArray()) {
            counter2[c-'a']++;
        }
        for (int i=0; i<26; i++) {
            if (counter1[i]!=counter2[i]) {
                return false;
            }
        }
        int N = s1.length();
        int prefixSum1 = 0;
        int prefixSum2 = 0, suffixSum2 = 0;
        for (int i=0; i<N; i++) {
            if (i>0 && prefixSum1==prefixSum2 && isScramble(s1.substring(0, i), s2.substring(0, i)) &&
                isScramble(s1.substring(i), s2.substring(i))) {
                return true;
            }
            if (i>0 && prefixSum1==suffixSum2 && isScramble(s1.substring(0, i), s2.substring(N-i)) &&
                isScramble(s1.substring(i), s2.substring(0, N-i))) {
                return true;
            }
            prefixSum1 += s1.charAt(i);
            prefixSum2 += s2.charAt(i);
            suffixSum2 += s2.charAt(N-1-i);
        }
        return false;
    }
}

Bottom-up

dp[l][i][j]表示isScramble(s1[i:i+l], s2[j:j+l])

Python:

class Solution:
    def isScramble(self, s1, s2):
        if len(s1)!=len(s2): return False
        N = len(s1)
        dp = [[[False]*N for _ in range(N)] for _ in range(N+1)]
        for l in range(1, N+1):
            for i in range(N-l+1):
                for j in range(N-l+1):
                    if dp[l][i][j]: continue
                    if s1[i:i+l]==s2[j:j+l]:
                        dp[l][i][j] = True
                        continue
                    for k in range(1, l):
                        if dp[k][i][j] and dp[l-k][i+k][j+k]:
                            dp[l][i][j] = True
                            break
                        if dp[k][i][j+l-k] and dp[l-k][i+k][j]:
                            dp[l][i][j] = True
                            break
        return dp[N][0][0]

Java:

class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.length()!=s2.length()) {
            return false;
        }
        int N = s1.length();
        boolean dp[][][] = new boolean[N+1][N][N];
        boolean hasLen[] = new boolean[N+1];
        
        for (int l=1; l<N+1; l++) {
            for (int i=0; i<N-l+1; i++) {
                for (int j=0; j<N-l+1; j++) {
                    if (dp[l][i][j])
                        continue;
                    if (s1.substring(i, i+l).equals(s2.substring(j, j+l))) {
                        dp[l][i][j] = true;
                        hasLen[l] = true;
                        continue;
                    }
                    for (int k=1; k<l; k++) {
                        if (!hasLen[k] || !hasLen[l-k]) {
                            continue;
                        }
                        if (dp[k][i][j] && dp[l-k][i+k][j+k]) {
                            dp[l][i][j] = true;
                            hasLen[l] = true;
                            break;
                        }
                        if (dp[k][i][j+l-k] && dp[l-k][i+k][j]) {
                            dp[l][i][j] = true;
                            hasLen[l] = true;
                            break;
                        }
                    }
                    
                }
            }
        }
        return dp[N][0][0];
    }
}