087.扰乱字符串
作者：沉默王二
发布时间：2023-10-08T16:33:18.362+0800
本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I
题意
使用下面描述的算法可以扰乱字符串 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"
解释：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"
示例 3：
输入：s1 = "a", s2 = "a"
分析
看到题目给的字符串生成方法，我们很容易想到，把每个可能的扰动字符串生成出来，再去比对，看答案是否就在其中。具体来说：
- 对于字符串 s1，可以选择任何一个非空位置进行分割，得到两个子串。
- 对于每一种分割，都可以选择交换这两个子串或不交换。
- 递归地对每个子串重复上面的操作。
- 如果在某一点，得到的扰乱序列与 s2 匹配，则返回 true。如果已经尝试了所有可能的序列都没有匹配，则返回 false。
来看具体的题解：
public class Solution {
// 如果两个字符串相等，直接返回 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) 是字符串的长度。
我们来观察一下题目给出的信息吧。
首先一个显而易见的结论是——如果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，使得：
- s1 是 t1 的扰乱字符串且 s2 是 t2 的扰乱字符串。
- 或者
- s1 是 t2 的扰乱字符串且 s2 是 t1 的扰乱字符串。
这两种情况考虑了可能的交换操作。但无论是哪种情况，都意味着 s 和 t 的子串必须是扰乱字符串。
针对本题，我们打算使用区间 DP，也就是区间动态规划。
区间动态规划 是动态规划的一个特定类别，主要用于解决需要处理字符串或数组中连续子段（或称为区间）的问题。在这类问题中，我们经常需要枚举所有可能的区间，并尝试通过某种方式组合这些区间来得到答案。
区间 DP 的特点通常包括以下几点：
- 状态表示：通常使用两个索引 i 和 j 来表示区间 [i, j]。例如，dp[i][j] 可以表示从 i 到 j 的某个值。
- 状态转移：为了计算 dp[i][j]，我们可能需要知道在该区间内的某个位置 k 的分割情况，然后根据 dp[i][k] 和 dp[k+1][j] 来计算。这通常涉及一个内部循环来枚举所有可能的 k。
- 初始化：较小的区间（如长度为1的区间）通常可以直接计算或由题目给出。这为我们提供了动态规划的基本情况。
- 计算顺序：由于某些区间的值可能依赖于较小的区间，所以计算的顺序是很重要的。通常，我们可能会先计算较小的区间，然后扩展到较大的区间。
扰乱字符串就属于经典的区间 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 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）
- 表示我们把长度为len的s和t分成两部分，一部分长度为k，另外一部分长度则为len-k，这时，k是它们的分隔点，且没有经过交换，即*「保持这两个子字符串的顺序不变」*的情况
- 表示k还是他们的分割点，但是这次是*「交换两个子字符串」*的情况。
最终的答案，存储在f[0][0][len]中，因为f[0][0][s.length]的含义就是从s的0位置开始，长度为s.length的字符串与t的从0位置开始，长度为s.length的字符串互为扰动字符串。
来看最终的题解。
class Solution {
// 如果两个字符串相等，直接返回 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](http://s1.length)()]，这表示整个 s1 和 s2 是否为扰乱字符串。
考虑两个字符串 s1 = "great" 和 s2 = "rgeat"。我们来验证 s2 是否是 s1 的扰乱字符串。
**1. 初始化：**
我们首先查看每个字符位置，如果 s1 和 s2 在该位置上的字符相同，则对应长度为1的子串标记为扰乱字符串。
s1 = g r 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开始)
通过上面的步骤，我们可以继续考虑更长的子串，并尝试所有可能的分割和交换，直到得出整个字符串是否为扰乱字符串。
来看题解的效率，还行。
### **总结**
动态规划的难点主要集中在如何找到 **状态** 和 **确定动态转移方程** 上，状态需要我们去认真观察，并且有时候需要去总结一些结论才能找出合适的状态，而动态转移方程，题目往往会以很规整的格式给出，我们需要学会细心总结。
力扣链接：**[https://leetcode.cn/problems/scramble-string/](https://leetcode.cn/problems/scramble-string/)**
### **一步一个脚印**
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对**[二哥编程星球](https://javabetter.cn/zhishixingqiu/)**的球友开放，如果你也想一起打卡学习算法的话，戳**[链接](https://javabetter.cn/zhishixingqiu/)**加入我们吧。
一个人可以走得很快，但一群人才能走得更远。**[二哥编程星球](https://javabetter.cn/zhishixingqiu/)**（目前已有 3600 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：[https://t.zsxq.com/6iuzn6I](https://t.zsxq.com/6iuzn6I)
### **题意**
使用下面描述的算法可以扰乱字符串 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"
解释：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"
**示例 3：**
输入：s1 = "a", s2 = "a"
### **分析**
看到题目给的字符串生成方法，我们很容易想到，把每个可能的扰动字符串生成出来，再去比对，看答案是否就在其中。具体来说：
- 对于字符串 s1，可以选择任何一个非空位置进行分割，得到两个子串。
- 对于每一种分割，都可以选择交换这两个子串或不交换。
- 递归地对每个子串重复上面的操作。
- 如果在某一点，得到的扰乱序列与 s2 匹配，则返回 true。如果已经尝试了所有可能的序列都没有匹配，则返回 false。
来看具体的题解：
public class Solution {
// 如果两个字符串相等，直接返回 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) 是字符串的长度。
我们来观察一下题目给出的信息吧。
首先一个显而易见的结论是——如果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，使得：
- s1 是 t1 的扰乱字符串且 s2 是 t2 的扰乱字符串。
- 或者
- s1 是 t2 的扰乱字符串且 s2 是 t1 的扰乱字符串。
这两种情况考虑了可能的交换操作。但无论是哪种情况，都意味着 s 和 t 的子串必须是扰乱字符串。
针对本题，我们打算使用区间 DP，也就是区间动态规划。
**区间动态规划** 是动态规划的一个特定类别，主要用于解决需要处理字符串或数组中连续子段（或称为区间）的问题。在这类问题中，我们经常需要枚举所有可能的区间，并尝试通过某种方式组合这些区间来得到答案。
区间 DP 的特点通常包括以下几点：
- **状态表示**：通常使用两个索引 i 和 j 来表示区间 [i, j]。例如，dp[i][j] 可以表示从 i 到 j 的某个值。
- **状态转移**：为了计算 dp[i][j]，我们可能需要知道在该区间内的某个位置 k 的分割情况，然后根据 dp[i][k] 和 dp[k+1][j] 来计算。这通常涉及一个内部循环来枚举所有可能的 k。
- **初始化**：较小的区间（如长度为1的区间）通常可以直接计算或由题目给出。这为我们提供了动态规划的基本情况。
- **计算顺序**：由于某些区间的值可能依赖于较小的区间，所以计算的顺序是很重要的。通常，我们可能会先计算较小的区间，然后扩展到较大的区间。
扰乱字符串就属于经典的区间 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 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）
- 表示我们把长度为len的s和t分成两部分，一部分长度为k，另外一部分长度则为len-k，这时，k是它们的分隔点，且没有经过交换，即*「保持这两个子字符串的顺序不变」*的情况
- 表示k还是他们的分割点，但是这次是*「交换两个子字符串」*的情况。
最终的答案，存储在f[0][0][len]中，因为f[0][0][s.length]的含义就是从s的0位置开始，长度为s.length的字符串与t的从0位置开始，长度为s.length的字符串互为扰动字符串。
来看最终的题解。
class Solution {
// 如果两个字符串相等，直接返回 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
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开始)
通过上面的步骤，我们可以继续考虑更长的子串，并尝试所有可能的分割和交换，直到得出整个字符串是否为扰乱字符串。
来看题解的效率，还行。
总结
动态规划的难点主要集中在如何找到 状态 和 确定动态转移方程 上，状态需要我们去认真观察，并且有时候需要去总结一些结论才能找出合适的状态，而动态转移方程，题目往往会以很规整的格式给出，我们需要学会细心总结。
力扣链接：https://leetcode.cn/problems/scramble-string/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3600 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I
题意
使用下面描述的算法可以扰乱字符串 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"
解释：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"
示例 3：
输入：s1 = "a", s2 = "a"
分析
看到题目给的字符串生成方法，我们很容易想到，把每个可能的扰动字符串生成出来，再去比对，看答案是否就在其中。具体来说：
- 对于字符串 s1，可以选择任何一个非空位置进行分割，得到两个子串。
- 对于每一种分割，都可以选择交换这两个子串或不交换。
- 递归地对每个子串重复上面的操作。
- 如果在某一点，得到的扰乱序列与 s2 匹配，则返回 true。如果已经尝试了所有可能的序列都没有匹配，则返回 false。
来看具体的题解：
public class Solution {
// 如果两个字符串相等，直接返回 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) 是字符串的长度。
我们来观察一下题目给出的信息吧。
首先一个显而易见的结论是——如果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，使得：
- s1 是 t1 的扰乱字符串且 s2 是 t2 的扰乱字符串。
- 或者
- s1 是 t2 的扰乱字符串且 s2 是 t1 的扰乱字符串。
这两种情况考虑了可能的交换操作。但无论是哪种情况，都意味着 s 和 t 的子串必须是扰乱字符串。
针对本题，我们打算使用区间 DP，也就是区间动态规划。
区间动态规划 是动态规划的一个特定类别，主要用于解决需要处理字符串或数组中连续子段（或称为区间）的问题。在这类问题中，我们经常需要枚举所有可能的区间，并尝试通过某种方式组合这些区间来得到答案。
区间 DP 的特点通常包括以下几点：
- 状态表示：通常使用两个索引 i 和 j 来表示区间 [i, j]。例如，dp[i][j] 可以表示从 i 到 j 的某个值。
- 状态转移：为了计算 dp[i][j]，我们可能需要知道在该区间内的某个位置 k 的分割情况，然后根据 dp[i][k] 和 dp[k+1][j] 来计算。这通常涉及一个内部循环来枚举所有可能的 k。
- 初始化：较小的区间（如长度为1的区间）通常可以直接计算或由题目给出。这为我们提供了动态规划的基本情况。
- 计算顺序：由于某些区间的值可能依赖于较小的区间，所以计算的顺序是很重要的。通常，我们可能会先计算较小的区间，然后扩展到较大的区间。
扰乱字符串就属于经典的区间 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 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）
- 表示我们把长度为len的s和t分成两部分，一部分长度为k，另外一部分长度则为len-k，这时，k是它们的分隔点，且没有经过交换，即*「保持这两个子字符串的顺序不变」*的情况
- 表示k还是他们的分割点，但是这次是*「交换两个子字符串」*的情况。
最终的答案，存储在f[0][0][len]中，因为f[0][0][s.length]的含义就是从s的0位置开始，长度为s.length的字符串与t的从0位置开始，长度为s.length的字符串互为扰动字符串。
来看最终的题解。
class Solution {
// 如果两个字符串相等，直接返回 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](http://s1.length)()]，这表示整个 s1 和 s2 是否为扰乱字符串。
考虑两个字符串 s1 = "great" 和 s2 = "rgeat"。我们来验证 s2 是否是 s1 的扰乱字符串。
**1. 初始化：**
我们首先查看每个字符位置，如果 s1 和 s2 在该位置上的字符相同，则对应长度为1的子串标记为扰乱字符串。
s1 = g r 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开始)
通过上面的步骤，我们可以继续考虑更长的子串，并尝试所有可能的分割和交换，直到得出整个字符串是否为扰乱字符串。
来看题解的效率，还行。
总结
动态规划的难点主要集中在如何找到 状态 和 确定动态转移方程 上，状态需要我们去认真观察，并且有时候需要去总结一些结论才能找出合适的状态，而动态转移方程，题目往往会以很规整的格式给出，我们需要学会细心总结。
力扣链接：https://leetcode.cn/problems/scramble-string/
一步一个脚印
不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。
PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。
一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3600 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！
知识星球
扫码加入星球
查看更多优质内容
https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412