【4.16】LeetCode每日一题· 扰乱字符串

2021年04月16日 17时24分

标签： LeetCode dfs 动态规划分治

## 题目描述
使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：
1. 如果字符串的长度为 1 ，算法停止
2. 如果字符串的长度 \> 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 由小写英文字母组成
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/scramble-string "题目链接")

## 解题思路
对于某一个字符串`s2`，我们可以**枚举**该字符串中每一个可能的**分割**位置，将其分成两个子串`left`和`right`。由于**扰乱字符串**是递归生成的，因此，如果`s2`是`s1`的扰乱字符串，那么`left`和`right`必定也是由`s1`的两个分割而成的子串`s1 = ls1 + rs1`生成的扰乱字符串，并且有以下两种情况
1. `left`和`right`分别是`ls1`和`rs1`的扰乱字符串，即将原字符串分割后，没有做【交换字符串】操作。
2. `left`和`right`分别是`rs1`和`ls1`的扰乱字符串，即将原字符串分割后，还做了一次【交换字符串】操作。

如果上述两种情况均不成立，则说明`s2`不是`s1`的扰乱字符串。而判断子串之间是否是扰乱字符串相对原问题来说是一个子问题，因此直接递归即可。递归边界为：
* 当两个子串长度为1且相同时，这两个字符串为扰乱字符串。

当然，如果只使用如上方法判断的时间复杂度为$$O(5^n)$$（原问题$$T(n) = 4(T(n-1) + T(n-2) + \cdots + T(1))$$），在$$n \leq 30$$的条件下TLE是必定的。注意到
1. 如果**两个串所含有的字符数不相同**，则这两个串一定**不是**扰乱字符串；
2. 如果**两个串相等**，则这两个串**必定是**扰乱字符串。
那么就可以做一些（徒劳无功的）剪枝操作。

**⚠️难点**：最后提交会发现还是TLE在倒数第三个点上。**此时应该考虑到，是否递归中求解的包含有重复的子问题**。实际上，在判断两个字符串是否为扰乱字符串的过程中，有很多子问题都是重复的。此时可以考虑到记忆画搜索，将**两个字符串是否为扰乱字符串**这一状态保存到`memory`数组中。递归过程中如果发现答案已被记录，则直接返回即可。由于这里的键为两个字符串，因此可以使用`map`嵌套`pair`实现。最终可以得到正确的代码。

如果将记忆化搜索再进一步，就可以得到正解的动态规划。详见[LeetCode官方题解](https://leetcode-cn.com/problems/scramble-string/solution/rao-luan-zi-fu-chuan-by-leetcode-solutio-8r9t/)。

Tips：这一道题今天做了一上午，递归搜索和剪枝操作已经完全敲了出来，甚至实现也由STL的`vector`改成了数组，但是始终是TLE，在这种情况下显然就不是常数级别的优化了，应该能想到一个比较普遍的搜索优化方法——记忆化搜索。但是直到下午还没有想到这一点，知道翻看了评论。对于记忆化搜索、以及dp还需要进一步的训练加强。

## 代码
```cpp
class Solution {
public:
    int cnt[26];
    vector<int> cnts1[31][31];
    vector<int> cnts2[31][31];
    map<pair<string, string>, bool> memory;

void getCnt(string& s1, string& s2){
        for(int i = 0; i < s1.length(); i++){
            // cout << "i = " << i << endl;
            cnts1[i][i].resize(26, 0);
            cnts2[i][i].resize(26, 0);
            cnts1[i][i][s1[i]-'a']++;
            cnts2[i][i][s2[i]-'a']++;
            for(int j = i+1; j < s1.length(); j++){
                // cout << "j = " << j << endl;
                cnts1[i][j] = cnts1[i][j-1];
                cnts1[i][j][s1[j]-'a']++;

cnts2[i][j] = cnts2[i][j-1];
                cnts2[i][j][s2[j]-'a']++;
            }
        }
    }
    
    bool check(string s1, string s2, int start_s1, int end_s1, int start_s2, int end_s2){
        if(memory.count({s1, s2})) return memory[{s1, s2}];
        const int N = s1.length();
        if(s1 == s2){
            return true;
        }

bool flag = false;
        // 枚举分点
        for(int i = 1; i < s2.length() && !flag; i++){
            string left = s2.substr(0, i);
            string right = s2.substr(i, N-i);

// 如果不交换，那么s2左边部分是s1左边部分的扰乱字符串，s2右边部分是s1右边部分的扰乱字符串
            if(cnts1[start_s1][start_s1+i-1] == cnts2[start_s2][start_s2+i-1] && cnts1[start_s1+i][end_s1-1] == cnts2[start_s2+i][end_s2-1]){
                flag = check(s1.substr(0, i), left, start_s1, start_s1+i, start_s2, start_s2+i) && check(s1.substr(i, N-1), right, start_s1+i, end_s1, start_s2+i, end_s2);
            }
            
            // 如果交换，那么s2左边部分是s1右边部分的扰乱字符串, s2右边部分是s1左边部分的扰乱字符串
            if(!flag){
                if(cnts1[end_s1-i][end_s1-1] == cnts2[start_s2][start_s2+i-1] && cnts1[start_s1][end_s1-i-1] == cnts2[start_s2+i][end_s2-1]){
                    flag = check(s1.substr(N-i, i), left, end_s1-i, end_s1, start_s2, start_s2+i) && check(s1.substr(0, N-i), right, start_s1, end_s1-i, start_s2+i, end_s2);
                }
            }
        }
        return memory[{s1, s2}] = flag;
    }

bool isScramble(string s1, string s2) {
        getCnt(s1, s2);
        return check(s1, s2, 0, s1.length(), 0, s2.length());
    }
};
```

## 用时和内存
> 执行用时：16 ms，在所有 C++提交中击败了57.16%的用户
> 内存消耗：18.8 MB，在所有 C++提交中击败了7.45%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.16】LeetCode每日一题· 扰乱字符串

所有评论

暂无评论

新增评论