LC

题目

思路

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

代码

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;
    }
};

时间复杂度分析

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

不妨设总时间复杂度为TnT_n,其中,nn为字符串的长度。

Tn=4(T1+T2++Tn1) T_n = 4(T_1 + T_2 + … + T_{n - 1}) ①
Tn1=4(T1+T2++Tn2) T_{n - 1} = 4(T_1 + T_2 + … + T_{n - 2}) ②
②得:① -②得:

TnTn1=4Tn1 T_n - T_{n - 1} = 4 T_{n - 1}
Tn=5Tn1 T_n = 5 T_{n - 1}
Tn=5n T_n = 5^n