跳转至

87. 扰乱字符串

难度:困难

题目

使用下面描述的算法可以扰乱字符串 s 得到字符串 t

  1. 如果字符串的长度为 1 ,算法停止
  2. 如果字符串的长度 > 1 ,执行下述步骤:
    • 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串 s ,则可以将其分成两个子字符串 xy ,且满足 s = x + y
    • 随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即,在执行这一步骤之后,s 可能是 s = x + y 或者 s = y + x
    • xy 这两个子字符串上继续从步骤 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
  • s1s2 由小写英文字母组成

Reference

题解

考虑两个字符串s1,s2s_1, s_2,函数f(x,y)f(x, y)定义如下:

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

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

  • f(s1,s2)=f(s2,s1)f(s_1, s_2) = f(s_2, s_1)
  • f(s1,s1)=Tf(s_1, s_1) = T
  • f(s1,s2)f(s2,s3)f(s1,s3)f(s_1, s_2) \land f(s_2, s_3)\rightarrow f(s_1, s_3)

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

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

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

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

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

如果s1,s2s_1, s_2的长度不匹配或字母出现次数不匹配,f(s1,s2)f(s_1, s_2)即可提前返回FF


考虑分割后的字符串,将s1s_1在下标ii与下标i+1i + 1处分割得到的两个字符串称为 s1,i,s1,is_{1, i}, s'_{1, i}s1,is_{1, i}位于左侧,s1,is'_{1, i}位于右侧。对于s2s_2,有同样的分割 方法得到s2,i,s2,is_{2, i}, s'_{2, i}。设字符串长度为ss,令i-i为从字符串右侧开始的下标ii

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

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

  • s1,is_{1, i}对应于s2,is_{2, i}s1,is'_{1, i}对应于s2,is'_{2, i}
  • s1,is_{1, i}对应于s2,is'_{2, -i}s1,is'_{1, i}对应于s2,is_{2, -i}

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

f(s1,s2)={F¬g(s1,s2)Ts3g(s1,s2)(if(s1,i,s2,i)f(s1,i,s2,i))(if(s1,i,s2,i)f(s1,i,s2,i))s>3g(s1,s2) 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 .

由此即可得出初步的算法,但多次递归会使得算法的时间复杂度上升,需要使用数组保存子问题的解。共有 O(n3)\mathcal O(n^3)规模的子问题,因此需要花费O(n3)\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);
}

评论