87. 扰乱字符串

发表于 分类于 阅读次数： Waline： 本文字数： 1.3k 阅读时长 ≈ 4 分钟

考点

  • 区间DP

思路

1. 问题描述

给定两个长度相同的字符串 \(s_1\) 与 \(s_2\)，判断 \(s_2\) 是否可以由 \(s_1\) 通过若干次“扰乱操作”得到。

扰乱操作定义如下：

  • 若字符串长度为 1，则不能再拆分；
  • 否则，可以将字符串拆分为左右两个非空连续子串；
  • 对左右子串可以选择：
    • 保持原顺序；
    • 或交换左右子串；
  • 对子串递归地继续进行扰乱。

问题要求判断：是否存在一系列合法的拆分与交换操作，使得 \(s_1\) 最终变为 \(s_2\)。

2. 建模思路：区间 DP 的必要性

2.1 递归结构的本质

扰乱字符串的定义本身具有明显的递归结构：

  • 每一次扰乱，都是将一个字符串区间拆成两个更小的连续区间；
  • 判断两个字符串是否“可扰乱”等价于：
    • 是否存在某种切分方式，使左右子区间两两对应（允许交换）且均可扰乱。

这天然对应区间动态规划（Interval DP）。

2.2 状态设计的关键问题

在区间 DP 中，核心在于回答两个问题：

  1. 一个状态应当描述什么子问题？
  2. 状态在转移时是否“封闭”？

本题中，必须同时刻画：

  • \(s_1\) 中的一个连续子串；
  • \(s_2\) 中与之比较的一个连续子串；
  • 两者的长度必须相同。

因此，最小且封闭的状态设计为： \[ \boxed{ f[i][j][\ell] \;=\; \text{表示 } s_1[i\,..\,i+\ell-1] \text{ 是否可以扰乱成 } s_2[j\,..\,j+\ell-1] } \] 其中：

  • \(i\)：\(s_1\) 中子串起点；
  • \(j\)：\(s_2\) 中子串起点；
  • \(\ell\)：子串长度。

这是本题区间 DP 的核心建模结论。

3. 边界条件（Base Case）

当子串长度为 1 时，不再允许拆分： \[ f[i][j][1] = \begin{cases} \text{true}, & s_1[i] = s_2[j] \\ \text{false}, & \text{otherwise} \end{cases} \] 这一步对应 DP 的初始化。

4. 状态转移方程的推导

4.1 区间拆分

考虑长度为 \(\ell \ge 2\) 的区间：

  • \(s_1[i\,..\,i+\ell-1]\)
  • \(s_2[j\,..\,j+\ell-1]\)

选择一个切分点 \(k\)（左半段长度）： \[ 1 \le k < \ell \] 将 \(s_1\) 拆为：

  • 左：\(s_1[i\,..\,i+k-1]\)，长度 \(k\)
  • 右：\(s_1[i+k\,..\,i+\ell-1]\)，长度 \(\ell-k\)

4.2 不交换的情况

左右子串保持顺序对应： \[ \begin{cases} s_1[i\,..\,i+k-1] \leftrightarrow s_2[j\,..\,j+k-1] \\ s_1[i+k\,..\,i+\ell-1] \leftrightarrow s_2[j+k\,..\,j+\ell-1] \end{cases} \] 对应 DP 条件： \[ f[i][j][k] \;\land\; f[i+k][j+k][\ell-k] \]

4.3 交换的情况

左右子串在 \(s_2\) 中发生交换： \[ \begin{cases} s_1[i\,..\,i+k-1] \leftrightarrow s_2[j+\ell-k\,..\,j+\ell-1] \\ s_1[i+k\,..\,i+\ell-1] \leftrightarrow s_2[j\,..\,j+\ell-k-1] \end{cases} \] 对应 DP 条件： \[ f[i][j+\ell-k][k] \;\land\; f[i+k][j][\ell-k] \]

4.4 完整状态转移方程

综合两种情况，只要存在某个 \(k\) 使得条件成立即可： \[ \boxed{ f[i][j][\ell] = \bigvee_{k=1}^{\ell-1} \left( \left( f[i][j][k] \land f[i+k][j+k][\ell-k] \right) \;\lor\; \left( f[i][j+\ell-k][k] \land f[i+k][j][\ell-k] \right) \right) } \] 这正是扰乱字符串问题的标准区间 DP 转移公式。

5. 计算顺序与复杂度分析

5.1 计算顺序

由于 \(f[i][j][\ell]\) 依赖于更小的长度：

  • 外层按 \(\ell = 1 \to n\) 枚举长度；
  • 内层枚举 \(i, j\)；
  • 最内层枚举切分点 \(k\)。

这是典型的按区间长度递增的区间 DP。

5.2 时间与空间复杂度

  • 状态数：\(O(n^3)\)
  • 每个状态枚举切分点：\(O(n)\)

\[ \text{时间复杂度} = O(n^4), \quad n \le 30 \text{ 可接受} \]

6. 参考实现（基于区间 DP）

下面给出一份与上述建模与转移一一对应的实现，并对代码逐行加注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    bool isScramble(string s1, string s2) {
        int n = s1.size();

        // f[i][j][len]:
        // 表示 s1 中从 i 开始、长度为 len 的子串
        // 是否可以扰乱成 s2 中从 j 开始、长度为 len 的子串
        // 这里使用 1-based 下标，便于区间计算
        bool f[35][35][35] = {};

        // 初始化：长度为 1 的区间
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                // 单字符是否相等
                f[i][j][1] = (s1[i - 1] == s2[j - 1]);
            }
        }

        // 按区间长度递增进行 DP
        for (int len = 2; len <= n; ++len) {
            for (int i = 1; i <= n - len + 1; ++i) {
                for (int j = 1; j <= n - len + 1; ++j) {

                    // 枚举切分点 k（左半段长度）
                    for (int k = 1; k < len; ++k) {

                        // 情况 1：不交换
                        // s1[i .. i+k-1]  <-> s2[j .. j+k-1]
                        // s1[i+k ..]      <-> s2[j+k ..]
                        if (f[i][j][k] && f[i + k][j + k][len - k]) {
                            f[i][j][len] = true;
                            break;
                        }

                        // 情况 2：交换左右子串
                        // s1[i .. i+k-1]  <-> s2[j+len-k .. j+len-1]
                        // s1[i+k ..]      <-> s2[j .. j+len-k-1]
                        if (f[i][j + len - k][k] && f[i + k][j][len - k]) {
                            f[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }

        // 判断整个字符串是否可以扰乱
        return f[1][1][n];
    }
};

7. 总结

  • 扰乱字符串问题的核心在于区间拆分 + 交换的递归结构；
  • 正确的 DP 状态必须同时记录：
    • 两个字符串的子串起点；
    • 子串长度；
  • 状态转移本质上是对“是否存在某个切分点 \(k\)”的枚举；
  • 三维区间 DP 是该问题最直接、最稳定的建模方式。