87. 扰乱字符串¶

难度：困难

题目¶

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

提示：

s1.length == s2.length
1 <= s1.length <= 30
s1 和 s2 由小写英文字母组成

Reference

题解¶

考虑两个字符串\(s_1, s_2\)，函数\(f(x, y)\)定义如下：

\[ f(x, y) = \left\{ \begin{aligned} & T & y\mathrm{是}x\mathrm{的扰乱字符串} \\ & F & y\mathrm{不是}x\mathrm{的扰乱字符串} \end{aligned} \right . \]

则对于函数\(f(x, y)\)，有如下性质：

\(f(s_1, s_2) = f(s_2, s_1)\)
\(f(s_1, s_1) = T\)
\(f(s_1, s_2) \land f(s_2, s_3)\rightarrow f(s_1, s_3)\)

即扰乱字符串关系是等价关系。

定义另一种等价关系\(g(x, y)\)：

\[ g(x, y) = \left\{ \begin{aligned} & T & x, y \mathrm{各字母出现次数相同} \\ & F & x, y \mathrm{各字母出现次数不同} \end{aligned} \right . \]

根据定义，扰乱字符串操作不会改变

字符串的长度
字符串内各字母的出现次数

如果\(s_1, s_2\)的长度不匹配或字母出现次数不匹配，\(f(s_1, s_2)\)即可提前返回\(F\)。

考虑分割后的字符串，将\(s_1\)在下标\(i\)与下标\(i + 1\)处分割得到的两个字符串称为 \(s_{1, i}, s'_{1, i}\)，\(s_{1, i}\)位于左侧，\(s'_{1, i}\)位于右侧。对于\(s_2\)，有同样的分割方法得到\(s_{2, i}, s'_{2, i}\)。设字符串长度为\(s\)，令\(-i\)为从字符串右侧开始的下标\(i\)。

根据算法，若任一组分割后的两个字符串满足扰乱字符串的关系，则原来的两个字符串满足扰乱字符串的关系，并且这两个字符串之间的关系与原字符串之间的关系无关，不会相互影响。因此可以采用动态规划，将原问题分割为一系列更小的子问题。

由于\(f(s_1, s_2)\)存在对称性，不妨固定\(s_1\)的分割方式，考虑\(s_2\)的分割方式。\(s_2\)有两种分割方式，即“保持子字符串顺序不变”或“交换两个子字符串”。分别对应于如下情况：

\(s_{1, i}\)对应于\(s_{2, i}\)，\(s'_{1, i}\)对应于\(s'_{2, i}\)。
\(s_{1, i}\)对应于\(s'_{2, -i}\)，\(s'_{1, i}\)对应于\(s_{2, -i}\)。

则\(f(s_1, s_2)\)可以按照如下方式计算，设\(\mathrm{len}(s_1) = \mathrm{len}(s_2) = s\)。

\[ f(s_1, s_2) = \left\{ \begin{aligned} & F & \lnot g(s_1, s_2) \\ & T & s\leq 3 \land g(s_1, s_2) \\ & \left(\bigvee_{i} f(s_{1, i}, s_{2, i})\land f(s'_{1, i}, s'_{2, i})\right) \lor \left(\bigvee_{i} f(s_{1, i}, s'_{2, -i})\land f(s'_{1, i}, s_{2, -i})\right) & s > 3 \land g(s_1, s_2)\\ \end{aligned} \right . \]

由此即可得出初步的算法，但多次递归会使得算法的时间复杂度上升，需要使用数组保存子问题的解。共有 \(\mathcal O(n^3)\)规模的子问题，因此需要花费\(\mathcal O(n^3)\)的时间复杂度与空间复杂度。

inline int hash(char *s, int len)
{
    int i, hashMap[26] = {0};
    unsigned long long ret = 0;
    for (i = 0; i < len; i++)
        hashMap[s[i] - 'a']++;
    for (i = 0; i < 26; i++)
    {
        ret *= 31;
        ret += hashMap[i] + 1;
        if (ret > INT_MAX)
            ret = ret & INT_MAX;
    }
    return (int)ret;
}

bool helper(char *s1, int offset1, char *s2, int offset2, int len, int ***dp)
{
    if (dp[offset1][offset2][len - 1] >= 0)
        return dp[offset1][offset2][len - 1];
    else if (len < 4)
    {
        dp[offset1][offset2][len - 1] = hash(s1 + offset1, len) == hash(s2 + offset2, len);
        return dp[offset1][offset2][len - 1];
    }
    int flag = false, a, i;
    dp[offset1][offset2][len - 1] = 0;
    for (i = 1; i < len; i++)
    {
        a = hash(s1 + offset1, i);
        if (a == hash(s2 + offset2, i))
            flag = flag || (
                helper(s1, offset1, s2, offset2, i, dp) && 
                helper(s1, offset1 + i, s2, offset2 + i, len - i, dp)
            );
        if (!flag && a == hash(s2 + offset2 + len - i, i))
            flag = flag || (
                helper(s1, offset1, s2, offset2 + len - i, i, dp) && 
                helper(s1, offset1 + i, s2, offset2, len - i, dp)
            );
        if (flag)
            break;
    }
    dp[offset1][offset2][len - 1] = flag;
    return dp[offset1][offset2][len - 1];
}

bool isScramble(char * s1, char * s2){
    int len = strlen(s1), i, j,
        ***dp = (int ***)malloc(sizeof(int **) * len),
        **_dp = (int **)malloc(sizeof(int *) * len * len),
        *__dp = (int *)malloc(sizeof(int) * len * len * len);
    memset(__dp, 0xff, sizeof(int) * len * len * len);
    for (i = 0; i < len; i++)
    {
        dp[i] = _dp + i * len;
        for (j = 0; j < len; j++)
            dp[i][j] = __dp + i * len * len + j * len;
    }
    return helper(s1, 0, s2, 0, strlen(s1), dp);
}

87. 扰乱字符串¶

题目¶

题解¶

评论