各位题友大家好！今天是 @负雪明烛 坚持日更的第 82 天。今天力扣上的每日一题是「87. 扰乱字符串」。

解题思路

递归

题意：「扰乱字符串」是指翻转 s1 中的某些子串，能否得到 s2.

这个题相当于让我们来判断两棵二叉树是否能够通过翻转某些子树而互相得到，也就是 951. Flip Equivalent Binary Trees 翻转二叉树子节点的题目。这个题不过是把树变成了字符串而已，不妨先通过 951 题的示意图来理解一下本题：

Flip Equivalent Binary Trees )

思路：从一个位置将两个字符串分别划分成两个子串，然后递归判断两个字符串的两个子串是否互相为「扰乱字符串」。

因为不知道在哪个位置分割字符串，所以直接遍历每个位置进行分割。在判断是否两个子串能否通过翻转变成相等的时候，需要保证传给函数的子串长度是相同的。

综上，因此分两种情况讨论：

s1[0:i]和 s2[0:i]作为左子树，s1[i:N]和 s2[i:N]作为右子树
s1[0:i]和 s2[N - i:N]作为左子树，s1[i:N]和 s2[0:N-i]作为右子树

其中左子树的两个字符串的长度都是 i, 右子树的两个字符串的长度都是 N - i。如果上面两种情况有一种能够成立，则 s1 和 s2 是「扰乱字符串」。

递归终止条件：当长度是 0、长度是 1 时的两个字符串是否相等进行判断。如果两个字符串本身包含的字符就不等，那么一定不是「扰乱字符串」，所以我们对两个字符串排序后是否相等也做判断。

记忆化递归

本题如果直接提交上面的递归解法，会超时，因为在不同的递归输入时，存在对相同子串的重复计算。避免重复计算的方式是使用「记忆化递归」。这个思路不难，就是把已经计算过的结果保存到缓存中，当此后再有同样的递归输入的时候，直接从缓存里面查，从而避免了重复计算。

在 Python 中，有一个实现记忆化递归的神器，就是 functool模块的 lru_cache装饰器，它可以把函数的输入和输出结果缓存住，在后续调用中如果遇到了相同的输入，直接从缓存里面读。顾名思义，它使用的是 LRU （最近最少使用）的缓存淘汰策略。

@functools.lru_cache(maxsize=None, typed=False)

maxsize 为最多缓存次数，如果为 None，则无限制；
typed=True 时，表示不同参数类型的调用将分别缓存。

该装饰器使用方法很简单，看下面代码的第二行。

这一行代码就能化腐朽为神奇，顺利 AC。

代码

下面给出了 Python 的代码。

class Solution:
    @functools.lru_cache(None)
    def isScramble(self, s1: str, s2: str) -> bool:
        N = len(s1)
        if N == 0: return True
        if N == 1: return s1 == s2
        if sorted(s1) != sorted(s2):
            return False
        for i in range(1, N):
            if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
                return True
            elif self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]):
                return True
        return False

时间复杂度：$O(N!)$，
空间复杂度：$O(N!)$

刷题心得

大多数情况下，动态规划能做的题目，也可以通过记忆化递归做。显然记忆化递归更简单。如果很难想到动态规划解法的话，不妨先写出递归解法，再写出记忆化递归解法，最后再想怎么转成动态规划。

参考资料：
87. Scramble String
Python 缓存机制与 functools.lru_cache

OK，以上就是 @负雪明烛写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！

算法每日一题题解

【每日一题】87. 扰乱字符串

解题思路

递归

记忆化递归

代码

刷题心得