题目描述

给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。

下图是字符串 s1 = "great" 的一种可能的表示形式。

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

我们将 "rgeat” 称作 "great" 的一个扰乱字符串。

同样地，如果我们继续交换节点 "eat" 和 "at" 的子节点，将会产生另一个新的扰乱字符串 "rgtae" 。

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

我们将 "rgtae” 称作 "great" 的一个扰乱字符串。

给出两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。

样例

输入: s1 = "great", s2 = "rgeat"
输出: true

输入: s1 = "abcde", s2 = "caebd"
输出: false

算法分析

假设字符串的长度是n，遍历所有可能的分割情况分割点 i 从 1 到n - 1，将s1分割成[0, i) [i, n)，对应s2匹配可能是[0, i)和[i, n)也可能是[n - i, n)和[0, n - i)。然后不断递归分割的子串直到s1 == s2 返回true。

时间复杂度 $O(5^n)$

Java 代码

class Solution {
    static String sort(String s)
    {
        char[] c = s.toCharArray();
        Arrays.sort(c);
        return String.valueOf(c);
    }
    public boolean isScramble(String s1, String s2) {
        if(s1.equals(s2)) return true;

        if(!sort(s1).equals(sort(s2))) return false;
        int n = s1.length();
        for(int i = 1;i <= n - 1;i ++)
        {
            if(isScramble(s1.substring(0, i), s2.substring(0, i)) 
                    && isScramble(s1.substring(i, n), s2.substring(i, n)))
                return true;

            if(isScramble(s1.substring(0, i), s2.substring(n - i, n))
                    && isScramble(s1.substring(i, n), s2.substring(0, n - i)))
                return true;
        }
        return false;
    }
}