题目描述

给定一个字符串 s1，将它表示成二叉树的形式：递归地每次将它拆分成两部分（非空）。
下面是"great"的一种二叉树表示：

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

为了打乱字符串，我们每次挑选一个非空节点，然后交换它的左右两个儿子。

例如，如果我们选择节点"gr"，然后交换它的左右两个节点，由此产生的字符串是"rgeat"。

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

我们说 "rgeat" 可以由 "great" 打乱而成。

同样的，如果我们继续交换节点"eat" 和 "at"，由此产生的字符串是 "rgtae"。

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

我们说 "rgtae" 也可以由 "great" 打乱而成。

现在给定两个等长的字符串 s1 和 s2，请判断 s1 是否可以由 s2 打乱而成。

样例1

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

样例2

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

算法1

(暴力搜索) $O(5^n)$ TLE

递归判断两个字符串是否可以相互转化。

首先判断两个字符串的字符集合是否相同，如果不同，则两个字符串一定不可以相互转化。
然后枚举第一个字符串左半部分的长度，分别递归判断两种可能的情况：

• 该节点不发生翻转，则分别判断两个字符串的左右两部分是否分别可以相互转化；
• 该节点发生翻转，则分别判断第一个字符串的左边是否可以和第二个字符串的右边相互转化，且第一个字符串的右边可以和第二个字符串的左边相互转化；

时间复杂度分析：设 $a_n$ 表示两个字符串长度是 $n$ 时的计算量，则根据递归函数，可知在最坏情况下：$a_n = 4\sum_{k=1}^{n-1}a_k$，列项相减可以得到 $a_n = 5a_{n-1}$，所以 $a_n = 5^n$。所以时间复杂度是 $O(5^n)$。

C++ 代码

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1 == s2) return true;
        string ss1 = s1, ss2 = s2;
        sort(ss1.begin(), ss1.end()), sort(ss2.begin(), ss2.end());
        if (ss1 != ss2) return false;
        for (int i = 1; i < s1.size(); i ++ )
        {
            if (isScramble(s1.substr(0, i), s2.substr(0, i))
                    && isScramble(s1.substr(i), s2.substr(i)))
                return true;
            if (isScramble(s1.substr(0, i), s2.substr(s2.size() - i))
                    && isScramble(s1.substr(i), s2.substr(0, s2.size() - i)))
                return true;
        }
        return false;
    }
};

算法2

DP $O(n^4)$ AC

1. 状态表示：f[i, j, k]
   1.1 集合：s1[i ~ i + k - 1]与s2[j, j + k - 1]所有匹配方案的集合
   1.2 属性：集合是否非空
2. 状态计算
   将f[i, j, k]表示的集合按s1第一段的长度划分划分成k - 1类。
   设s1第一段的长度为u。则s1[i ~ i + k - 1]与s2[j, j + k - 1]有两种匹配方案，分别判断即可：
   (1) f[i][j][u] && f[i + u][j + u][k - u]
   (2) f[i][j + k - u][u] && f[i + u][j][k - u]

时间复杂度分析：状态数 $O(n^3)$，状态转移计算量为 $O(n)$，所以总时间复杂度为 $O(n^4)$。

C++ 代码

class Solution {
public:
    bool isScramble(string s1, string s2) {
        int n = s1.size();
        vector<vector<vector<bool>>> f(n, vector<vector<bool>>(n, vector<bool>(n + 1)));
        for (int k = 1; k <= n; k ++ )
            for (int i = 0; i + k - 1 < n; i ++ )
                for (int j = 0; j + k - 1 < n; j ++ ) {
                    if (k == 1) {
                        if (s1[i] == s2[j]) f[i][j][k] = true;
                    } else {
                        for (int u = 1; u < k; u ++ ) {
                            if (f[i][j][u] && f[i + u][j + u][k - u] || f[i][j + k - u][u] && f[i + u][j][k - u]) {
                                f[i][j][k] = true;
                                break;
                            }
                        }
                    }
                }
        return f[0][0][n];
    }
};