---

0087. 扰乱字符串

• 标签：字符串、动态规划
• 难度：困难

题目链接

• 0087. 扰乱字符串 - 力扣

题目大意

描述：

使用下面描述的算法可以扰乱字符串 $s$ 得到字符串 $t$：

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

给定两个长度相等的字符串 $s1$ 和 $s2$。

要求：

判断 $s2$ 是否是 $s1$ 的扰乱字符串。如果是，返回 $true$；否则，返回 $false$。

说明：

• $s1.length == s2.length$。
• $1 \le s1.length \le 30$。
• $s1$ 和 $s2$ 由小写英文字母组成。

示例：

• 示例 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

解题思路

思路 1：动态规划

核心思想：

使用三维动态规划来解决扰乱字符串问题。定义 $dp[i][j][k]$ 表示 $s1$ 从位置 $i$ 开始长度为 $k$ 的子串，是否可以通过扰乱操作得到 $s2$ 从位置 $j$ 开始长度为 $k$ 的子串。

算法步骤：

1. 状态定义：$dp[i][j][k]$ 表示 $s1[i:i+k]$ 是否可以通过扰乱得到 $s2[j:j+k]$。
2. 边界条件：当 $k = 1$ 时，$dp[i][j][1] = (s1[i] == s2[j])$。
3. 状态转移：对于长度 $k$ 的子串，尝试所有可能的分割点 $l$（$1 \le l < k$）：
   • 不交换情况：$dp[i][j][l] \land dp[i+l][j+l][k-l]$
   • 交换情况：$dp[i][j+k-l][l] \land dp[i+l][j][k-l]$
4. 最终结果：$dp[0][0][n]$ 即为答案。

关键点：

• 需要枚举所有可能的分割点 $l$，其中 $l$ 表示左子串的长度
• 对于每个分割点，考虑交换和不交换两种情况
• 使用记忆化搜索或自底向上的动态规划来避免重复计算

思路 1：代码

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        """
        判断 s2 是否是 s1 的扰乱字符串
        使用动态规划方法
        """
        n = len(s1)
        if n != len(s2):
            return False
        
        # 三维 DP 数组：dp[i][j][k] 表示 s1[i:i+k] 是否可以通过扰乱得到 s2[j:j+k]
        dp = [[[False] * (n + 1) for _ in range(n)] for _ in range(n)]
        
        # 边界条件：长度为 1 的子串
        for i in range(n):
            for j in range(n):
                dp[i][j][1] = (s1[i] == s2[j])
        
        # 动态规划：枚举所有可能的长度和分割点
        for k in range(2, n + 1):  # 子串长度从 2 到 n
            for i in range(n - k + 1):  # s1 的起始位置
                for j in range(n - k + 1):  # s2 的起始位置
                    # 尝试所有可能的分割点 l (1 <= l < k)
                    for l in range(1, k):
                        # 情况 1：不交换，左子串对应左子串，右子串对应右子串
                        if dp[i][j][l] and dp[i + l][j + l][k - l]:
                            dp[i][j][k] = True
                            break
                        
                        # 情况 2：交换，左子串对应右子串，右子串对应左子串
                        if dp[i][j + k - l][l] and dp[i + l][j][k - l]:
                            dp[i][j][k] = True
                            break
        
        return dp[0][0][n]

思路 1：复杂度分析

• 时间复杂度：$O(n^4)$，其中 $n$ 是字符串长度。需要四重循环：长度 $k$、起始位置 $i$ 和 $j$、分割点 $l$，每重循环最多 $n$ 次。
• 空间复杂度：$O(n^3)$，需要 $O(n^3)$ 空间存储三维 DP 数组。