problem:87. 扰乱字符串

思路：很容易就能想到，我们可以枚举s1字符串的长度，然后又可以分为两种情况，要么就是不交换两个子串，要么就交换两个子串。定义f[i][j][k]为s1以i为起点s2以j为起点长度为k的子串是否能构成扰乱字符串。状态转移看代码就可。

Accode:

class Solution {
public:
    string  s1,s2;
    int memo[31][31][31];
    bool dfs(int i,int j,int k){
        // if(k==0) return true;
        if(k==1){
            return s1[i]==s2[j]?true:false;
        }
        if(memo[i][j][k]!=-1) return memo[i][j][k];
        for(int len=1;len<k;len++){
            if(dfs(i,j,len)&&dfs(i+len,j+len,k-len)){
                return memo[i][j][k] = true;
            }
            if(dfs(i,j+k-len,len)&&dfs(i+len,j,k-len)){
                return memo[i][j][k] = true;
            }
        }
        return memo[i][j][k] = false;
    }
    bool isScramble(string s1, string s2) {
        if(s1.length()!=s2.length()) return false;
        vector<int> cnts1(26),cnts2(26);
        for(int i=0;i<s1.length();i++){
            cnts1[s1[i]-'a']++;
            cnts2[s2[i]-'a']++;
        }
        for(int i=0;i<cnts1.size();i++){
            if(cnts1[i]!=cnts2[i]) return false;
        }
        this->s1 = s1;
        this->s2 = s2;
        memset(memo,-1,sizeof memo);
        return dfs(0,0,s1.length());
    }
};

时间复杂度：$o(n^4)$