0087 - Scramble String

题干

问题描述

破题

源代码

因为这道题是 3k点赞，1k点踩， 于是看了下评论，结果为我的解题带来了非常大的负面影响：有一个评论里讲什么这道题的题解非常困难，但是用4套嵌套循环实现非常简单，这一直影响我的思路。

然而实际上这只是一道普通的 Top-down DP，或者说，记忆化搜索就可以通过的题目。

另外让人不爽地是这个文本：“Randomly decide to swap the two substrings……” ，随机地决定这种说法就很误导，让人搞不清问题到底是个什么类型的问题。

实际上这个问题很简单，把串按位置划分，从 $1\dots n-1 $，确保得到的两个子串的长度至少为 $1$；

而这两个子串有两种可能：保持原序或者颠倒顺序；

然后试着对子串继续应用这个划分，直到子串的长度为 $1$ 。

最终目的是检查 $s_1$ 能否变换到 $s_2$ 。

解①：

这个问题天然地适合利用递归解决，只不过可以通过保存一些中间结果来进行优化。

具体说就是遍历每一个划分子串的位置，然后对划分后的两种情况：原序和反序，分别进行判断。

对于原序，就是检查较小规模地同一问题 $s_1[0..i-1]$ 能够变换到 $s_2[0..i-1]$ ；以及 $s_1[i..n-1]$ 能够变换到 $s_2[i..n-1]$ ；

对于反序，就是检查$s_1[0..i-1]$ 能够变换到 $s_2[n-i..n-1]$；以及 $s_1[i..n-1]$ 能够变换到 $s_2[0..n-i-1]$ 。

from functools import cache

@cache
def solve(s1: str, s2: str) -> bool:
    if sorted(s1) != sorted(s2):
        return False

    n = len(s1)

    if n == 1:
        return s1 == s2

    for i in range(1, n):
        if (
            solve(s1[:i], s2[n - i :])
            and solve(s1[i:], s2[: n - i])
            or solve(s1[:i], s2[:i])
            and solve(s1[i:], s2[i:])
        ):
            return True

    return False

特别地，这里检查了字符集合是否相等，作为一个快速失败地（预测）优化¹。

运行时间：58 ms (beats 78.15%, ~100%)，内存占用：17.9 MB (beats 36.12%, ~100%)。

注解