leetcode日记（74）扰乱字符串

很有难度的一题，一开始真的绕了很多思维上的弯路。

最开始的想法是递归，看到题目的时候想到动态规划但是完全没有思路应该怎么用，结果确实是递归+动态规划。

最开始的想法是构建树，每一层包含这一步划分的方法（实际会很复杂，时间绝对超限，于是就放弃了）。

然后用贴近动态规划的思维思考，想要构建一个二（三）维表格，先对角线存放每一个字母，然后一层层推出两两结合的可能性……（怎么比第一种还要复杂啊啊啊啊）

最后还是看了答案，答案的动态规划+递归+剪枝思路还是很巧妙的。

动态规划其实是构建了这么一个数组：memo[i1][i2][len]，其中i1、i2表示分别从两个字符串的i1i2起，各取len个字母，这两个取出来的字符串是否为扰乱字符串。

一开始i1、i2取0，len取最大长度（就是直接塞入题目的问题），然后开始层层递归。

递归时建立一个循环，将i1后移，i2后移（如果不交换）或从最末端前移（如果交换），len就随之变化。

以上只是最基础的思路。

既然是动态规划，那么数组肯定还可以重复使用，保存的数组就是为了这个操作：if(memo[i1][i2][len]!=0) return memo[i1][i2][len]==1;

注意这里，memo有三种状态，-1（不是扰乱字符串）、1（是扰乱字符串）、0（未计算）。

这里这样做可以重复使用之前的数据，节省很多复杂度。

为了进一步降低时间复杂度，还得进行剪枝。

方法是再建立一个判断”是否可能为扰乱字符串“的判断，如果其中有某个字母，在两个字符串中出现的频次不等，那么就不可能是扰乱字符串。

我原以为写这个会有些复杂，没想到可以用map写：

bool peace(string s1, string s2){
        unordered_map<char, int> freq;
        for(int i=0;i<s1.length();i++){
            freq[s1[i]]++;
        }
        for(int i=0;i<s2.length();i++){
            freq[s2[i]]--;
        }
        if(any_of(freq.begin(),freq.end(),[](auto& n){return n.second!=0;})) return 0;
        else return 1;
    }

使用unorder_map，记录第一个字符串中出现的单词频率，再遍历第二个字符串，将出现的单词减一，如果最后存在个数不为0的单词，即不可能为扰乱字符串。

最后代码：

class Solution {
    string s1,s2;
    int memo[30][30][31];
public:
    bool peace(string s1, string s2){
        unordered_map<char, int> freq;
        for(int i=0;i<s1.length();i++){
            freq[s1[i]]++;
        }
        for(int i=0;i<s2.length();i++){
            freq[s2[i]]--;
        }
        if(any_of(freq.begin(),freq.end(),[](auto& n){return n.second!=0;})) return 0;
        else return 1;
    }
    bool dfs(int i1, int i2, int len){
        if(memo[i1][i2][len]!=0) return memo[i1][i2][len]==1;
        if(s1.substr(i1,len)==s2.substr(i2,len)) {memo[i1][i2][len]=1;return 1;}
        if(peace(s1.substr(i1,len), s2.substr(i2,len))==0) {memo[i1][i2][len]=0;return 0;}
        for(int i=1;i<len;i++){
            if(dfs(i1,i2,i)&&dfs(i1+i,i2+i,len-i)){
                memo[i1][i2][len] = 1;
                return 1;
            }
            if(dfs(i1,i2+len-i,i)&&dfs(i1+i,i2,len-i)){
                memo[i1][i2][len] = 1;
                return 1;
            }
        }
        memo[i1][i2][len]=-1;
        return 0;
    }
    bool isScramble(string s1, string s2) {
        memset(memo,0,sizeof(memo));
        this->s1=s1;
        this->s2=s2;
        return dfs(0,0,s1.length());        
    }
};

（基本是照着答案写的真的很抱歉）