LC-87 扰乱字符串

题目

思路

此题考察的是递归求解问题的思维，从扰乱字符串的定义也可以看出，扰乱操作是像二叉树一样一层层向下进行的。所以可以考虑枚举一下每次切分的点，切分后的左右子串和模式串的对应位置进行匹配，这形成了一个递归问题。

代码

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if(s1 == s2) return true;
        string bs1 = s1, bs2 = s2;
        sort(bs1.begin(), bs1.end()), sort(bs2.begin(), bs2.end());
        if(bs1 != bs2) return false;

        int n = s1.size();
        for(int i = 1; i < n; 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(n - i)) &&
               isScramble(s1.substr(i), s2.substr(0, n - i))) return true;
        }
        return false;
    }
};

时间复杂度分析

不过这题值得讨论的是时间复杂度的计算。关于递归函数的时间复杂度通常需要通过递推式来求解。

不妨设总时间复杂度为$T_n$，其中，$n$为字符串的长度。

$$T_n = 4(T_1 + T_2 + … + T_{n - 1}) ①$$
$$T_{n - 1} = 4(T_1 + T_2 + … + T_{n - 2}) ②$$
$$① -②得：$$

$$T_n - T_{n - 1} = 4 T_{n - 1}$$
$$T_n = 5 T_{n - 1}$$
$$T_n = 5^n$$

• Post author: Jacky.C
• Post link: https://scnujackychen.github.io/2021/03/11/LC-87/
• Copyright Notice: All articles in this blog are licensed under unless otherwise stated.