题目描述

给出两个长度相等的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。

样例

示例 1:
输入: s1 = "great", s2 = "rgeat"
输出: true

示例 2:
输入: s1 = "abcde", s2 = "caebd"
输出: false

算法1

(递归模拟) $O(5^n)$

见参考文献。

时间复杂度

见参考文献，这个时间复杂度还是略显风骚hh。

参考文献

https://www.acwing.com/solution/content/170/

C++ 代码

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        if (s1 == s2) return true;

        // 统计s1,s2字母是否一致
        vector<int> c1(26), c2(26);
        for (char c: s1) ++c1[c - 'a'];
        for (char c: s2) ++c2[c - 'a'];

        for (int i = 0; i < 26; ++i)
            if (c1[i] != c2[i]) return false;

        // 枚举翻转位置
        for (int i = 1; i < s1.size(); ++i){
            // 不翻转的情况
            if (isScramble(s1.substr(0, i), s2.substr(0, i)) && 
                isScramble(s1.substr(i), s2.substr(i))) return true;
            // 翻转的情况
            if (isScramble(s1.substr(0, i), s2.substr(s2.size() - i)) && 
                isScramble(s1.substr(i), s2.substr(0, s1.size() - i))) return true;
        }

        return false;
    }
};

算法2

(记忆化搜索) $O(?)$

以上有递归暴力求解，时间复杂度是指数级别；
可以通过改写成记忆化搜索，优化效率。

时间复杂度

时间复杂度很难直接分析，但是改写成动态规划以后，就非常好分析了。

参考文献

C++ 代码

class Solution {
private:
    unordered_map<string, bool> memo;
public:
    bool isScramble(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        if (s1 == s2) return true;

        if (memo.count(s1 + '#' + s2)) return memo[s1 + '#' + s2];


        // 统计s1,s2字母是否一致
        vector<int> c1(26), c2(26);
        for (char c: s1) ++c1[c - 'a'];
        for (char c: s2) ++c2[c - 'a'];

        for (int i = 0; i < 26; ++i)
            if (c1[i] != c2[i]) return false;

        // 枚举翻转位置
        for (int i = 1; i < s1.size(); ++i){
            // 不翻转的情况
            if (isScramble(s1.substr(0, i), s2.substr(0, i)) && 
                isScramble(s1.substr(i), s2.substr(i))) {
                memo[s1 + '#' + s2] = true;
                return true;
            }
            // 翻转的情况
            if (isScramble(s1.substr(0, i), s2.substr(s2.size() - i)) && 
                isScramble(s1.substr(i), s2.substr(0, s1.size() - i))) {
                memo[s1 + '#' + s2] = true;
                return true;
            }
        }

        memo[s1 + '#' + s2] = false;
        return false;
    }
};

算法3

(动态规划) $O(n ^ 4)$

有记忆化搜索的方法，自然就会联想到有没有显式的动态规划递推可以求解。
状态表示：
$f[i][j][k]$表示，$s1[i, i + k)$与$s2[j, j + k)$是否互为扰乱字符串。

状态转移：
$s1[i, i + k)$可以在$[i + 1, i + k - 1)$的任意位置扰乱，所以需要枚举扰乱位置$l$；
对于所有的扰乱位置，$s1$和$s2$都分为前半部分和后半部分，我们需要前前匹配并且后后匹配，或者前后匹配、后前匹配，故有：
$f[i][j][k] = (f[i][j][k]) || (f[i][j][l] and f[i + l][j + l][k - l]) || (f[i][j + k - l][l] and f[i + l][j][k - l])$

时间复杂度

状态数$O(n^3)$，转移需要$O(n)$，故总时间复杂度$O(n^4)$。

参考文献

https://leetcode-cn.com/problems/scramble-string/solution/miao-dong-de-qu-jian-xing-dpsi-lu-by-sha-yu-la-jia/

C++ 代码

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        if (s1 == s2) return true;

        // 统计s1,s2字母是否一致
        vector<int> c1(26), c2(26);
        for (char c: s1) ++c1[c - 'a'];
        for (char c: s2) ++c2[c - 'a'];

        for (int i = 0; i < 26; ++i)
            if (c1[i] != c2[i]) return false;

        int n = s1.size();
        bool f[n][n][n + 1];
        memset(f, false, sizeof f);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (s1[i] == s2[j])
                    f[i][j][1] = true;

        for (int k = 2; k <= n; ++k)
            for (int i = 0; i <= n - k; ++i)
                for (int j = 0; j <= n - k; ++j)
                    for (int l = 1; l < k; ++l)
                        // cout << i << " " << j << " " << k << ": " << f[i][j][k] << endl;
                        f[i][j][k] = f[i][j][k] || f[i][j][l] && f[i + l][j + l][k - l] || f[i][j + k - l][l] && f[i + l][j][k - l];

        return f[0][0][n];
    }
};