# 0087. 扰乱字符串

### 题目地址(87. 扰乱字符串)

<https://leetcode-cn.com/problems/scramble-string/>

### 题目描述

```
使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：
如果字符串的长度为 1 ，算法停止
如果字符串的长度 > 1 ，执行下述步骤：
在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。

给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。

 

示例 1：

输入：s1 = "great", s2 = "rgeat"
输出：true
解释：s1 上可能发生的一种情形是：
"great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串
"gr/eat" --> "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」
"gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
"g/r / e/at" --> "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」
"r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法，将 "at" 分割得到 "a/t"
"r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」
算法终止，结果字符串和 s2 相同，都是 "rgeat"
这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true


示例 2：

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


示例 3：

输入：s1 = "a", s2 = "a"
输出：true


 

提示：

s1.length == s2.length
1 <= s1.length <= 30
s1 和 s2 由小写英文字母组成
```

### 前置知识

* 动态规划
* 递归

### 公司

* 暂无

### 思路

我们可以将 s1 和 s2 看成是两颗树 t1 和 t2 的中序遍历结果。

这样问题转为为**t1 是否可由 t2 经过翻转任意节点得到**，这里的翻转某一节点指的是交换该节点的左右子树，使得原本的左子树变成右子树，右子树变为左子树。这和 [951. 翻转等价二叉树](https://leetcode-cn.com/problems/flip-equivalent-binary-trees/) 是一样的。

而这道题比那道题难的点在于是**不知道树的原始结构**。我们可以将枚举所有可能，以 s1 来说：

* s1 的第一个字符可能是整棵树的根节点
* s1 的第二个字符可能是整棵树的根节点
* 。。。

确定了根节点，我们只需要使用同样的方法即可确定其他节点。这提示我们使用递归来解决。

> 如果对上面如何构造树不懂的，可以看下我之前写的 [构造二叉树](https://lucifer.ren/blog/2020/02/08/%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%93%E9%A2%98/)

上面提到了互为扰乱字符串必然存在相同的字符种类和个数，因此当我们确定了 s1 的根节点的时候，s2 的根节点只有两种类型。这是因为 s2 要保证分割后两部分的大小分别和 s1 的两部分大小完全一样。也就是说：**我们没有必要枚举 s1 和 s2 的所有可能的根节点组合**（这种组合有 n ^ 2 种，其中 n 为 s1 和 s2 的长度），而是**仅仅枚举 s1 的割点**（这样只有 n 种）。

实际上，我们没有必要先构造树 t1 和 t2，再去判断**t1 是否可由 t2 经过翻转任意节点得到**。而是将两个步骤结合到一起进行。

接下来，我们对 t1 的**每一个节点都执行进行翻转或者不翻转两种操作**，如果最终 t1 和 t2 相等了，说明 s1 和 s2 互为干扰字符串。实际上，我们没有必要真的翻转，而是直接比较 t1 的左子树和 t2 的右子树，t1 的右子树和 t2 的左子树**是否完全一样**。

代码：

> 我直接复制的 [951. 翻转等价二叉树](https://leetcode-cn.com/problems/flip-equivalent-binary-trees/) 的代码

```py
class Solution:
    def flipEquiv(self, root1: TreeNode, root2: TreeNode) -> bool:
        if not root1 or not root2:
            return not root1 and not root2
        if root1.val != root2.val:
            return False
        # 不翻转
        if self.flipEquiv(root1.left, root2.left) and self.flipEquiv(root1.right, root2.right):
            return True
        # 翻转
        if self.flipEquiv(root1.left, root2.right) and self.flipEquiv(root1.right, root2.left):
            return True
        # 不管翻转还是不翻转都不行，直接返回 False
        return False
```

另外，由于扰乱字符串的定义我们不难知道：如果 s1 和 s2 的字符种类和个数不完全相同，那么不可能是互为扰乱字符串（也就是说 s1 和 s2 排序后需要保持相同）。我们可以利用这点剪枝。

### 关键点

* 将其抽象为树的对比问题

### 代码

* 语言支持：Python3

Python3 Code:

```python

class Solution:
    @lru_cache(None)
    def isScramble(self, s1: str, s2: str) -> bool:
        if s1 == s2:
            return True
        # 剪枝
        if collections.Counter(s1) != collections.Counter(s2):
            return False
        # 枚举所有可能的根节点
        for i in range(1, len(s1)):
            # ----|-
            # -|----
            # 不进行翻转
            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
                return True
            # 进行翻转
            if self.isScramble(s1[i:], s2[:-i]) and self.isScramble(s1[:i], s2[-i:]):
                return True
        # 不管翻转还是不翻转都不行，直接返回 False
        return False


```

**复杂度分析**

令 n 为字符串长度。

* 时间复杂度：$O(n^4)$， 其中 $n^3$ 来自于 isScramble 的计算次数，$n$ 来内每次 isScramble 的计算量。
* 空间复杂度：$O(n^3)$， 内存占用全部来自记忆化部分，因此空间复杂度等于数据规模，也就是 isScramble 三个参数的规模乘积。

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/nsfsko.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/87.scramble-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.