题目

题解

1. 递归法

就是通过递归左右子串，首先判断长度是否相等，不相等直接false；然后判断是否完全一样，一样直接true；然后判断排序后是否相等，不相等也false，接下来分两种情况递归，
即1左=2左且1右=2右，
或1左=2右且1右=2左，
=表示互为scramble，细节见注释

class Solution {
public:
   bool isScramble(string s1, string s2) {
       if(s1.size() != s2.size()) return false;//长度不一样，直接返回false
       if(s1 == s2) return true;//完全一样，返回true
       string sort_s1 = s1, sort_s2 = s2;
       sort(sort_s1.begin(), sort_s1.end());
       sort(sort_s2.begin(), sort_s2.end());
       if(sort_s1 != sort_s2) return false;//比较两个排序后的数组，不一样直接返回false
       for(int i=1; i<s1.size(); ++i){
           //在每个点对两个字符串进行划分，然后进行递归对比，有两种情况，具体看题解和下面
           string s11 = s1.substr(0,i);
           string s12 = s1.substr(i);
           string s21 = s2.substr(0,i);
           string s22 = s2.substr(i);
           if(isScramble(s11,s21) && isScramble(s12,s22)) return true;//情况一
           //注意这两行，情况二的s2左右子串长度于情况一相反
           s21 = s2.substr(0, s1.size()-i);
           s22 = s2.substr(s1.size()-i);
           if(isScramble(s11,s22) && isScramble(s12,s21)) return true;//情况二
       }
       return false;//若全部遍历完还没有返回true说明不是scramble，返回false
   }
};

2. 动态规划

炒鸡难，看了(https://www.cnblogs.com/grandyang/p/4318500.html)和(https://leetcode-cn.com/problems/scramble-string/solution/miao-dong-de-qu-jian-xing-dpsi-lu-by-sha-yu-la-jia/)才懂得，那个状态转移矩阵比较麻烦，而且是三维的dp，详细看上述博客和注释吧。

  • 时间复杂度$O(n^{4})$，三维dp矩阵和一个状态转移时的遍历
  • 空间复杂度$O(n^{3})$，三维dp
//动态规划，这个有点难了，其实原理和递归类似，也是判断划分后左右的子串是否是scramble
class Solution {
public:
    bool isScramble(string s1, string s2) {
        if(s1.size() != s2.size()) return false;//长度不一样，直接返回false
        if(s1 == s2) return true;//完全一样，返回true
        int n = s1.size();

        //创建三维状态转移数数组,len是n+1.其中0是空的，长度为0的不考虑，1~n有值
        //其实这个数组应该是一个四分之一的金字塔形，越往上越小,下面内层的两个循环用n-len就说明这一点
        //可以在脑中想象这个图形
        //int dp[n][n][n+1];
        vector<vector<vector<bool>>> dp(n,vector<vector<bool>>(n,vector<bool>(n+1,false)));

        for(int len=1; len<=n; ++len){
            for(int i=0; i<=n-len; ++i){
                for(int j=0; j<=n-len; ++j){
                    if(len == 1) dp[i][j][len] = (s1[i] == s2[j]);
                    else{
                        for(int k=1; k<len; ++k){//遍历每一种劈法
                            //状态转移方程，只要有一种劈法1左=2左且1右=2右，或1左=2右且1右=2左就可以，=表示互为scramble
                            //注意第二种情况的括号内的数字，两个不完全一样，一个+k，一个+len-k
                            if((dp[i][j][k] && dp[i+k][j+k][len-k])||(dp[i][j+k][len-k] && dp[i+len-k][j][k])){
                                dp[i][j][len] = true;
                                break;//有一种情况成立就可以break
                            }
                        }
                    }
                }
            }
        }
        return dp[0][0][n];
    }
};