Luobuyu's Blog

0%

87.扰乱字符串

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 2.4k 阅读时长 ≈ 2 分钟
使用动态规划，但是递推方程递推顺序比较难确定，可以使用记忆化搜索规避这一问题。

87.扰乱字符串

题目描述：

使用以下方法扰乱字符串 $s$ 得到字符串 $t$ ：

  1. 如果字符串的长度为 $1$ ，算法终止

  2. 如果长度大于 $1$ ，按照以下顺序执行：

    • 在随机下标处将 $s$ 分割为 $x,y$ ;

    • 随机组合得到 $x+y$ 或者 $y + x$ ；

    • 继续对生成的字符串执行上述操作

给出两个长度相等的字符串 $s1,s2$ ，判断 $s2$ 是否是 $s1$ 经过扰乱产生的。

数据范围：
$1\le n\le 30$

题解：

如果长度不同，或者同一个字符出现的次数不同则一定不能产生。如果两个字符串相同直接返回。

其他的情况需要对字符串进行分割。需要枚举分割点，将 $s1$ 分割为 $x1,x2$ ，将 $s2$ 分割为 $y1,y2$ 。判断 $(x1,y1)(x2,y2)$ 或者 $(x1,y2)(x2,y1)$ 是否是通过扰动产生。

可以使用 $dp[index1][index2][len]$ 来表示以 $s1[index1],s2[index2]$ 为起点的长度为 $len$ 的字符串是否是通过扰动产生的。

那么

不方便枚举，可以使用记忆化搜索。

如果使用递推需要确定枚举 $i,j,len$ 的顺序以及初始化条件。其实就是一个区间 $dp$ 。

初始条件为：只有一个字符并且相等则为 $true$ 。即 $dp[i][j][1] = true;s1[i]=s2[j]$

枚举顺序：

  • 先枚举 $len$ ，因为后面的长度需要更小的长度的结果。 $2\le len \le n$
  • 因为长度更短的已经算出来了，所以 $i$ 和 $j$ 的枚举顺序没有要求。

这个题目由于有效状态比较少，记忆化搜索的速度更快。

代码：

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
class Solution
{
public:
    int dp[30][30][31];
    int cnt[26];
    bool check(int index1, int index2, int len, string &s1, string &s2)
    {
        for (int i = 0; i < 26; ++i)
            cnt[i] = 0;
        for (int i = 0; i < len; ++i)
        {
            cnt[s1[index1 + i] - 'a']++;
            cnt[s2[index2 + i] - 'a']--;
        }
        for (int i = 0; i < 26; ++i)
        {
            if (cnt[i] != 0)
                return false;
        }
        return true;
    }
    bool dfs(int index1, int index2, int len, string &s1, string &s2)
    {
        if (dp[index1][index2][len])
            return dp[index1][index2][len] == 1;
        if (s1.substr(index1, len) == s2.substr(index2, len))
            return dp[index1][index2][len] = 1, true;
        // 判断是否存在某个字符出现次数不同
        if (!check(index1, index2, len, s1, s2))
        {
            return dp[index1][index2][len] = -1, false;
        }
        for (int i = 1; i < len; ++i)
        {
            if (dfs(index1, index2, i, s1, s2) && dfs(index1 + i, index2 + i, len - i, s1, s2))
                return dp[index1][index2][len] = 1, true;
            if (dfs(index1, index2 + len - i, i, s1, s2) && dfs(index1 + i, index2, len - i, s1, s2))
                return dp[index1][index2][len] = 1, true;
        }
        return dp[index1][index2][len] = -1, false;
    }

    bool isScramble(string s1, string s2)
    {
        return dfs(0, 0, s1.size(), s1, s2) == 1;
    }
};
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
class Solution
{
public:
    int dp[30][30][31];

    bool isScramble(string s1, string s2)
    {
        int n = s1.length();
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (s1[i] == s2[j])
                    dp[i][j][1] = true;
            }
        }
        for (int len = 2; len <= n; ++len)
        {
            for (int i = 0; i + len - 1 < n; ++i)
            {
                for (int j = 0; j + len - 1 < n; ++j)
                {
                    for (int k = 1; k < len; ++k)
                    {
                        if (dp[i][j][k] && dp[i + k][j + k][len - k] || dp[i][j + len - k][k] && dp[i + k][j][len - k])
                        {
                            dp[i][j][len] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[0][0][n];
    }
};