87. 扰乱字符串

题意

使用下面描述的算法可以扰乱字符串 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 。

难度

困难

示例

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

分析

看到题目给的字符串生成方法，我们很容易想到，把每个可能的扰动字符串生成出来，再

去比对，看答案是否就在其中。具体来说：

1. 对于字符串 s1，可以选择任何一个非空位置进行分割，得到两个子串。

2. 对于每一种分割，都可以选择交换这两个子串或不交换。

3. 递归地对每个子串重复上面的操作。

4. 如果在某一点，得到的扰乱序列与 s2 匹配，则返回 true。如果已经尝试了所有可能

的序列都没有匹配，则返回 false。

来看具体的题解：

public class Solution {

public boolean isScramble(String s1, String s2) {

// 如果两个字符串相等，直接返回 true

if (s1.equals(s2)) {

return true;

}

// 如果两个字符串的字符不一致，返回 false

int[] letters = new int[26];

for (int i = 0; i < s1.length(); i++) {

letters[s1.charAt(i) - 'a']++;

letters[s2.charAt(i) - 'a']--;

}

for (int i = 0; i < 26; i++) {

if (letters[i] != 0) {

return false;

}

}

// 尝试每一种分割和交换的组合

for (int i = 1; i < s1.length(); i++) {

// 不交换的情况

if (isScramble(s1.substring(0, i), s2.substring(0, i)) &&

isScramble(s1.substring(i), s2.substring(i))) {

return true;

}

// 交换的情况

if (isScramble(s1.substring(0, i), s2.substring(s2.length() - i)) &&

isScramble(s1.substring(i), s2.substring(0, s2.length() - i))) {

return true;

}

}

return false;

}

}

这种暴力解法很好理解，但时间复杂度是非常高的，对于每一个位置，都有两种可能的操

作（交换或不交换），因此时间复杂度约为 (O(2^n))，其中 (n) 是字符串的长度。

087.%E6%89%B0%E4%B9%B1%E5%AD%97%E7%AC%A6%E4%B8%B2-

20231008152955.png

我们来观察一下题目给出的信息吧。

首先一个显而易见的结论是——如果 s 为 t 的扰动字符串，那么 t 也是 s 的扰动字符串。

随机** 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不

变」。即，在执行这一步骤之后，**s** 可能是 **s = x + y** 或者 **s = y +

x** 。**

在 s 转化为 t 的过程中，如果是交换两个子字符串，t 转化为 s 也只需要交换两个子字符串

就可以，如果是保持两个子字符串的顺序不变，则 t 转化为 s 同样也只需要子字符串的顺

序不变即可。

因此我们可以得出第一个结论：

如果**s**为**t**的扰动字符串，那么**t**也是**s**的扰动字符串。

举个简单的例子来说明这一点：

假设有两个字符串 s = "great" 和 t = "rgeat"，我们知道 t 是 s 的扰乱字符串，因为我们

可以将 s 分割为 gr | eat，然后交换这两个子串得到 t。

但是，我们也可以将 t 分割为 rg | eat，然后再次交换这两个子串，这样就可以得到 s。

因此，我们可以说 s 也是 t 的扰乱字符串。

第二个结论也好得出，只不过需要加上一点点小的思考：

如果**s**和**t**互为扰动字符串，那么它们的子串中肯定存在互为扰动字符串

的子串。

考虑字符串 s 和 t。如果 s 是 t 的扰乱字符串，那么在某个点，我们必须对 s 进行一次分

割得到 s1 和 s2，并对 t 进行一次分割得到 t1 和 t2，使得：

1. s1 是 t1 的扰乱字符串且 s2 是 t2 的扰乱字符串。

或者

2. s1 是 t2 的扰乱字符串且 s2 是 t1 的扰乱字符串。

这两种情况考虑了可能的交换操作。但无论是哪种情况，都意味着 s 和 t 的子串必须是扰

乱字符串。

针对本题，我们打算使用区间 DP，也就是区间动态规划。

区间动态规划 是动态规划的一个特定类别，主要用于解决需要处理字符串或数组中连续

子段（或称为区间）的问题。在这类问题中，我们经常需要枚举所有可能的区间，并尝试

通过某种方式组合这些区间来得到答案。

区间 DP 的特点通常包括以下几点：

1. 状态表示：通常使用两个索引 i 和 j 来表示区间 [i, j]。例如，dp[i][j] 可以表示从 i 到

j 的某个值。

2. 状态转移：为了计算 dp[i][j]，我们可能需要知道在该区间内的某个位置 k 的分割情

况，然后根据 dp[i][k] 和 dp[k+1][j] 来计算。这通常涉及一个内部循环来枚举所有

可能的 k。

3. 初始化：较小的区间（如长度为 1 的区间）通常可以直接计算或由题目给出。这为我

们提供了动态规划的基本情况。

4. 计算顺序：由于某些区间的值可能依赖于较小的区间，所以计算的顺序是很重要的。

通常，我们可能会先计算较小的区间，然后扩展到较大的区间。

扰乱字符串就属于经典的区间 DP 问题，我们来看看这道题的状态表示、状态转移、初始

化和计算顺序。

首先我们可以创建一个 f[i][j][k][l]的四维数组，来表示从 i 到 j 的字符串 s 的字串，判断

其是否跟从 k 到 l 的字符串 t 的字串互为扰动字符串，

因为 s 和 t 互为扰动字符串，长度必然相等，所以我们可以节省一维，只用 f[i][j][len] 表

示从 i 开始的长度为 len 的 s 的子串跟从 j 开始的长度为 len 的 t 的子串互为扰动字符串。

做动态规划题，在明确了 状态（表示每个阶段开始所处的自然状况或客观条件） 之后，

接下来要做的就是确定初始状态。

我们从最小的情况来考虑，就是子串长度为 1 的情况，如果二者互为扰动字符串，没有别

的选择，必须是 s[i] == t[j]。

所以初始状态就是：

for (int i = 0;i < s1.length();i++)

for (int j = 0;j < s2.length();j++)

if (s1.charAt(i) == s2.charAt(j))

f[i][j][1] = true;

搞定了初始状态，我们就要考虑接下来的动态转移方程了。

观察题目的条件 “随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺

序不变」。即，在执行这一步骤之后，_s_ 可能是 _s = x + y_ 或者 _s = y + x_ 。”

假设 s = x1 + y1，t = x2 + y2，要判断 s 和 t 互为扰动字符串，需要判断以下两种情

况：

• x1 与 x2 互为扰动字符串，且 y1 与 y2 互为扰动字符串

• x1 与 y2 互为扰动字符串，且 y1 与 x2 互为扰动字符串

上述两种情况分别对应了「保持这两个子字符串的顺序不变」和 「交换两个子字符串」

的情况。

我们可以不断找出 s 和 t 的所有拆分方法，然后依次判断这其中是否存在能使得上述两种

情况成立的一个可行办法，只要有，s 和 t 就互为扰动字符串。

所以动态转移方程就是：

$

$

详细解释一下这个动态转移方程：（以下讲解中把从 i 开始，长度为 len 的 s1 的子串记为

s，从 j 开始，长度为 len 的 s2 的子串记为 t）

• $ [f(i,j,k) & f(i+k,j+k,len-k)] $ 表示我们把长度为 len 的 s 和 t 分成两部分，一部分长度

为 k，另外一部分长度则为 len-k，这时，k 是它们的分隔点，且没有经过交换，即_

「保持这两个子字符串的顺序不变」_的情况

• $ f(i,j+len-k,k) & f(i+k,j,len-k) $ 表示 k 还是他们的分割点，但是这次是_「交换两个子

字符串」_的情况。

最终的答案，存储在 f[0][0][len]中，因为 f[0][0][s.length]的含义就是从 s 的 0 位置开

始，长度为 s.length 的字符串与 t 的从 0 位置开始，长度为 s.length 的字符串互为扰动字

符串。

来看最终的题解。

class Solution {

public boolean isScramble(String s1, String s2) {

// 如果两个字符串相等，直接返回 true

if (s1.equals(s2)){

return true;

}

// 如果两个字符串的长度不相同，那么它们不能是扰乱字符串，返回 false

if (s1.length() != s2.length()){

return false;

}

// f[i][j][len] 表示从 s1 的第 i 位开始、从 s2 的第 j 位开始、长度为 len 的子串，是否为

扰乱字符串

 boolean[][][] f = new boolean[s1.length()][s2.length()][s1.length() + 1];

// 初始化：如果 s1 和 s2 的相应位置字符相同，则长度为 1 的子串是扰乱字符串

for (int i = 0;i < s1.length();i++)

for (int j = 0;j < s2.length();j++)

if (s1.charAt(i) == s2.charAt(j))

f[i][j][1] = true;

// 外层循环：遍历所有可能的子串长度

for (int len = 2;len <= s1.length();len++)

// i 和 j 是两个子串的起始位置

for (int i = 0;i <= s1.length() - len;i++)

for (int j = 0;j <= s2.length() - len;j++) {

// k 是区间 [i, i+len) 和 [j, j+len) 的划分点

for (int k = 1;k < len;k++) {

// 检查是否存在一种划分方式，使得两个子串是扰乱字符串

if ((f[i][j][k] && f[i + k][j + k][len - k])

|| (f[i][j + len - k][k] && f[i + k][j][len - k])) {

f[i][j][len] = true;

break;

}

}

}

// 返回整个 s1 和 s2 是否为扰乱字符串

return f[0][0][s1.length()];

}

}

解释：

• 我们使用一个三维数组 f 来保存状态，其中 f[i][j][len] 表示从 s1 的第 i 位开始、从

s2 的第 j 位开始、长度为 len 的子串是否为扰乱字符串。

• 我们首先初始化长度为 1 的子串。如果 s1 和 s2 的相应位置上的字符相同，那么这两

个子串显然是扰乱字符串。

• 之后，我们从长度为 2 的子串开始，逐渐增加子串的长度。对于每一种长度，我们枚

举所有可能的起始位置 i 和 j，然后尝试所有可能的分割方式（通过变量 k）。

• 对于每一种分割方式，我们检查是否存在一种情况，使得两个子串是扰乱字符串。这

可以是 f[i][j][k] 和 f[i + k][j + k][len - k] 都为 true，或者是 f[i][j + len - k][k] 和 f[i

+ k][j][len - k] 都为 true。这两种情况分别对应于不交换和交换两个子串。

• 最后，我们返回 f[0][0][s1.length()]，这表示整个 s1 和 s2 是否为扰乱字符串。

考虑两个字符串 s1 = "great" 和 s2 = "rgeat"。我们来验证 s2 是否是 s1 的扰乱字符

串。

1. 初始化：

我们首先查看每个字符位置，如果 s1 和 s2 在该位置上的字符相同，则对应长度为 1 的子

串标记为扰乱字符串。

s1 = g r e a t

s2 = r g e a t

f = F F T T T (对于长度为 1 的子串)

2. 扩展到长度为 2 的子串：

我们看 s1 的前两个字符 “gr” 和 s2 的前两个字符 “rg”。由于 “g” 和 “r” 可以交换位置，所

以 “gr” 和 “rg” 互为扰乱字符串。

s1 = g r e a t

| |

s2 = r g e a t

| |

f = T (对于长度为 2 的子串，从位置 0 开始)

3. 扩展到更长的子串：

接下来，我们可以考虑长度为 3 的子串 “gre” 和 “rge”。由于 “gr” 和 “rg” 互为扰乱字符

串，并且它们后面的字符 “e” 是相同的，所以 “gre” 和 “rge” 也互为扰乱字符串。

s1 = g r e a t

| | |

s2 = r g e a t

| | |

f = T (对于长度为 3 的子串，从位置 0 开始)

通过上面的步骤，我们可以继续考虑更长的子串，并尝试所有可能的分割和交换，直到得

出整个字符串是否为扰乱字符串。

来看题解的效率，还行。

087.%E6%89%B0%E4%B9%B1%E5%AD%97%E7%AC%A6%E4%B8%B2-

20231008161127.png

总结

动态规划的难点主要集中在如何找到 状态 和 确定动态转移方程 上，状态需要我们去认真

观察，并且有时候需要去总结一些结论才能找出合适的状态，而动态转移方程，题目往往

会以很规整的格式给出，我们需要学会细心总结。

力扣链接：https://leetcode.cn/problems/scramble-string/