0087. Scramble String
=====================
题目信息
--------
:题号: 0087. 扰乱字符串
:难度: Hard
:主题: 字符串、记忆化搜索、区间动态规划
:原题: `LeetCode 0087 `_
:重点: 从递归枚举切分,推导到三维状态缓存与区间动态规划
题目重述
--------
给定两个字符串 ``s1`` 和 ``s2``。对一个长度大于 1 的字符串,可以在任意位置把它切成两个非空子串,
然后选择保持左右顺序或交换左右子串,再对两个子串递归执行相同操作。
判断 ``s2`` 能否由 ``s1`` 经过上述操作得到。两个字符串只包含小写英文字母,长度均不超过 30。
自建示例
--------
.. code-block:: text
输入:s1 = "abc", s2 = "bca"
输出:true
把 ``abc`` 切为 ``a | bc``,交换两个部分后得到 ``bc | a``,即 ``bca``。
.. code-block:: text
输入:s1 = "abcd", s2 = "bdac"
输出:false
两个字符串字符频次相同,但不存在一棵递归切分树,使每个节点都能通过保持或交换两个孩子完成对应。
.. code-block:: text
输入:s1 = "great", s2 = "rgeat"
输出:true
可以把 ``great`` 切为 ``gr | eat``。左侧 ``gr`` 交换为 ``rg``,右侧 ``eat`` 保持不变。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
std::string first;
std::string second;
std::vector> first_prefix;
std::vector> second_prefix;
std::vector>> memo;
void buildPrefixCounts() {
int n = static_cast(first.size());
first_prefix.assign(n + 1, {});
second_prefix.assign(n + 1, {});
for (int index = 0; index < n; ++index) {
first_prefix[index + 1] = first_prefix[index];
second_prefix[index + 1] = second_prefix[index];
++first_prefix[index + 1][first[index] - 'a'];
++second_prefix[index + 1][second[index] - 'a'];
}
}
bool sameCharacters(int first_start, int second_start, int length) const {
for (int letter = 0; letter < 26; ++letter) {
int first_count = first_prefix[first_start + length][letter] -
first_prefix[first_start][letter];
int second_count = second_prefix[second_start + length][letter] -
second_prefix[second_start][letter];
if (first_count != second_count) {
return false;
}
}
return true;
}
bool equalRange(int first_start, int second_start, int length) const {
for (int offset = 0; offset < length; ++offset) {
if (first[first_start + offset] != second[second_start + offset]) {
return false;
}
}
return true;
}
bool plainRecursion(int first_start, int second_start, int length) {
if (equalRange(first_start, second_start, length)) {
return true;
}
if (!sameCharacters(first_start, second_start, length)) {
return false;
}
for (int split = 1; split < length; ++split) {
bool keep_order =
plainRecursion(first_start, second_start, split) &&
plainRecursion(first_start + split,
second_start + split,
length - split);
bool swap_order =
plainRecursion(first_start,
second_start + length - split,
split) &&
plainRecursion(first_start + split,
second_start,
length - split);
if (keep_order || swap_order) {
return true;
}
}
return false;
}
bool memoizedRecursion(int first_start, int second_start, int length) {
int& cached = memo[first_start][second_start][length];
if (cached != -1) {
return cached == 1;
}
if (equalRange(first_start, second_start, length)) {
cached = 1;
return true;
}
if (!sameCharacters(first_start, second_start, length)) {
cached = 0;
return false;
}
for (int split = 1; split < length; ++split) {
bool keep_order =
memoizedRecursion(first_start, second_start, split) &&
memoizedRecursion(first_start + split,
second_start + split,
length - split);
bool swap_order =
memoizedRecursion(first_start,
second_start + length - split,
split) &&
memoizedRecursion(first_start + split,
second_start,
length - split);
if (keep_order || swap_order) {
cached = 1;
return true;
}
}
cached = 0;
return false;
}
bool intervalDp(const std::string& s1, const std::string& s2) {
int n = static_cast(s1.size());
std::vector>> dp(
n,
std::vector>(
n,
std::vector(n + 1, false)));
for (int first_start = 0; first_start < n; ++first_start) {
for (int second_start = 0; second_start < n; ++second_start) {
dp[first_start][second_start][1] =
s1[first_start] == s2[second_start];
}
}
for (int length = 2; length <= n; ++length) {
for (int first_start = 0; first_start + length <= n; ++first_start) {
for (int second_start = 0;
second_start + length <= n;
++second_start) {
for (int split = 1; split < length; ++split) {
bool keep_order =
dp[first_start][second_start][split] &&
dp[first_start + split]
[second_start + split]
[length - split];
bool swap_order =
dp[first_start]
[second_start + length - split]
[split] &&
dp[first_start + split]
[second_start]
[length - split];
if (keep_order || swap_order) {
dp[first_start][second_start][length] = true;
break;
}
}
}
}
}
return dp[0][0][n];
}
public:
bool isScramble(std::string s1, std::string s2) {
if (s1.size() != s2.size()) {
return false;
}
first = s1;
second = s2;
int n = static_cast(first.size());
buildPrefixCounts();
memo.assign(
n,
std::vector>(
n,
std::vector(n + 1, -1)));
return memoizedRecursion(0, 0, n);
}
};
题解
----
递归切分
~~~~~~~~
一个扰乱过程可以看成一棵二叉树。树中每个节点保存一段字符串,并在某个位置切成左右两个非空部分。
根节点对子节点只有两种安排:保持左右顺序,或交换左右顺序。
令状态 ``solve(i, j, length)`` 表示:
.. code-block:: text
s1[i : i + length]
能否扰乱成:
.. code-block:: text
s2[j : j + length]
在 ``split`` 处分割第一个区间后,保持顺序时需要同时满足:
.. code-block:: text
solve(i, j, split)
solve(i + split, j + split, length - split)
交换顺序时,第一个区间左侧应对应第二个区间末尾同样长的部分:
.. code-block:: text
solve(i, j + length - split, split)
solve(i + split, j, length - split)
只要某个切分点的一种安排中两个子状态都成立,当前状态就成立。
必要条件剪枝
~~~~~~~~~~~~
扰乱操作只改变子串位置,不会改变字符多重集。两个对应区间的字符频次不同,当前状态必定失败。
逐状态重新扫描区间会产生额外重复。前缀频次数组保存每个字符在任意前缀中的出现次数,区间频次可由两次前缀相减得到,
每次剪枝只需比较 26 个字符。
两个区间内容完全相同时,可以直接返回成功,不必继续枚举切分点。剪枝顺序因此是:
.. code-block:: text
区间完全相等 -> 成功
字符频次不同 -> 失败
其余情况 -> 枚举切分点
重复状态
~~~~~~~~
不同的上层切分可能到达相同的 ``(i, j, length)``。朴素递归会反复求解这些区间,搜索树随长度快速膨胀。
三维缓存为每个状态保存未知、失败、成功三种结果。失败状态同样必须缓存,否则大量无法匹配的区间仍会被重复搜索。
区间动态规划
~~~~~~~~~~~~
记忆化搜索按需要访问状态。自底向上的写法使用同一个三维定义:
.. code-block:: text
dp[i][j][length]
长度为 1 时,只需比较两个字符。长度大于 1 的状态只依赖两个更短区间,因此按 ``length`` 从小到大填表即可。
两种写法拥有相同的状态和转移。记忆化搜索能利用频次剪枝跳过大量不可达状态,通常更直接;区间 DP 没有递归调用,遍历顺序更固定。
正确性
~~~~~~
任意合法扰乱树的根节点必有一个切分点,并且根节点只可能保持或交换两个孩子。算法枚举全部切分点和这两种安排,
因此合法扰乱不会遗漏。
反过来,算法只有在某个切分点的两个子状态都成立时才返回成功。把两个子状态对应的合法扰乱树连接到当前根节点,
即可构造当前区间的合法扰乱树,因此不会产生错误的成功结果。
复杂度
~~~~~~
状态数为 ``O(n^3)``,每个状态最多枚举 ``O(n)`` 个切分点,记忆化搜索和区间 DP 的时间上界均为 ``O(n^4)``。
前缀频次剪枝每次比较固定 26 个字符,不改变渐进复杂度。
三维缓存或 DP 表使用 ``O(n^3)`` 空间;记忆化搜索的递归深度为 ``O(n)``。朴素递归没有缓存,最坏呈指数增长。