LeetCode 87. 扰乱字符串
题目描述
题意分析
每次把字符串切成两个非空连续部分，可以保留它们的先后顺序，也可以整体交换，再分别递归处理两部分。判断
s2能否这样由s1得到。操作保留每个字符的数量，但不允许任意重排，因此频次相同只是必要条件。
解法：记忆化搜索（递归划分 + 剪枝）
核心思路
[!blue]
用
dfs(i1, i2, len)表示：s1从i1开始、长度为len的片段，能否扰乱得到s2从i2开始的同长度片段。结果只由这三个量决定，与如何到达这个子问题无关，因此可以记忆化，避免不同切法重复求解相同片段。枚举第一串前半段的长度
k，范围为1到len - 1。若当前层不交换，第一串的前k个字符对应第二串的前k个，剩余部分也一一对应，条件是dfs(i1, i2, k)与dfs(i1 + k, i2 + k, len - k)同时为真。若当前层交换，第一串前
k个字符被放到目标片段的末尾，所以它在第二串的起点为i2 + len - k；第一串后len - k个字符则对应目标开头。条件变为dfs(i1, i2 + len - k, k)与dfs(i1 + k, i2, len - k)同时为真。任意一种切点和交换选择成功，就能拼出当前目标；反过来，任何合法扰乱都必然有这样的第一层划分，因此枚举不会遗漏。搜索前先做两种剪枝：两段完全相同，可以递归保持各部分顺序，直接返回真；字符频次不同，无论如何交换都无法弥补，直接返回假。长度为 1 时必然被其中一种情况处理；其余递归长度严格减小，保证结束。
缓存需要区分“未计算、成功、失败”。Java 用可为
null的Boolean数组，Go 用seen区分是否求过，再由memo保存布尔结果。失败也要缓存，否则无解片段仍会被反复展开。
解题步骤
- 长度不同则返回假，否则初始化缓存，从
dfs(0, 0, n)开始。- 若状态已有缓存，直接返回；否则先判断两段相同或字符频次不同，并缓存相应结果。
- 枚举所有非空切分，依次检查不交换和交换两种配对。某种配对的两个子问题都成功时，缓存真并返回。
- 所有切法都失败，缓存假并返回。只满足某一侧不足以构造完整目标，两侧必须同时成立。
代码实现
class Solution {
private String s1;
private String s2;
private Boolean[][][] memo;
public boolean isScramble(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
this.s1 = s1;
this.s2 = s2;
int n = s1.length();
memo = new Boolean[n][n][n + 1];
return dfs(0, 0, n);
}
// 状态由两串起点与共同长度确定，切点两侧必须同时成立
private boolean dfs(int i1, int i2, int len) {
if (memo[i1][i2][len] != null) {
return memo[i1][i2][len];
}
if (s1.regionMatches(i1, s2, i2, len)) {
memo[i1][i2][len] = true;
return true;
}
// 频次不符直接缓存失败，之后不再重复展开同一状态
if (!sameCount(i1, i2, len)) {
memo[i1][i2][len] = false;
return false;
}
for (int k = 1; k < len; k++) {
if (dfs(i1, i2, k) && dfs(i1 + k, i2 + k, len - k)) {
memo[i1][i2][len] = true;
return true;
}
// 交换时前 k 个字符对应第二串末尾 k 个，而非从 k 处开始
if (dfs(i1, i2 + len - k, k) && dfs(i1 + k, i2, len - k)) {
memo[i1][i2][len] = true;
return true;
}
}
memo[i1][i2][len] = false;
return false;
}
private boolean sameCount(int i1, int i2, int len) {
int[] cnt = new int[26];
for (int k = 0; k < len; k++) {
cnt[s1.charAt(i1 + k) - 'a']++;
cnt[s2.charAt(i2 + k) - 'a']--;
}
for (int x : cnt) {
if (x != 0) {
return false;
}
}
return true;
}
}
func isScramble(s1 string, s2 string) bool {
if len(s1) != len(s2) {
return false
}
n := len(s1)
memo := make(map[[3]int]bool)
seen := make(map[[3]int]bool)
var sameCount func(i1, i2, length int) bool
sameCount = func(i1, i2, length int) bool {
var cnt [26]int
for k := 0; k < length; k++ {
cnt[s1[i1+k]-'a']++
cnt[s2[i2+k]-'a']--
}
for i := 0; i < 26; i++ {
if cnt[i] != 0 {
return false
}
}
return true
}
var dfs func(i1, i2, length int) bool
// 状态由两串起点与共同长度确定，切点两侧必须同时成立
dfs = func(i1, i2, length int) bool {
key := [3]int{
i1,
i2,
length,
}
if seen[key] {
return memo[key]
}
seen[key] = true
if s1[i1:i1+length] == s2[i2:i2+length] {
memo[key] = true
return true
}
// 频次不符直接缓存失败，之后不再重复展开同一状态
if !sameCount(i1, i2, length) {
memo[key] = false
return false
}
for k := 1; k < length; k++ {
if dfs(i1, i2, k) && dfs(i1+k, i2+k, length-k) {
memo[key] = true
return true
}
// 交换时前 k 个字符对应第二串末尾 k 个，而非从 k 处开始
if dfs(i1, i2+length-k, k) && dfs(i1+k, i2, length-k) {
memo[key] = true
return true
}
}
memo[key] = false
return false
}
return dfs(0, 0, n)
}
复杂度分析
- 时间复杂度：$O(n^4)$ 上界，其中 $n$ 为字符串长度。共有 $O(n^3)$ 个起点与长度状态，每个状态至多花 $O(n)$ 检查片段、统计频次和枚举切点；已计算的子问题直接查缓存。
- 空间复杂度：$O(n^3)$，主要来自记忆化缓存，递归深度最多为 $O(n)$。
关键点总结
[!green]
- 状态必须区分未计算、真、假。
- 当前切点两侧用与连接，不同切法之间用或。
易错点总结
[!yellow]
- 交换分支定位第二串尾部时，长度减切点写错会配错片段。
- 切点含零或全长，子问题不再严格缩小。
- 只比较频次就返回，忽略递归切分约束。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 241. 为运算表达式设计优先级 | 中等 | 同样枚举区间分割点并组合左右子问题，本题还要比较交换与不交换两种对应。 |