扰乱字符串（递归思想，区间dp做法）

扰乱字符串

递归思想

不管想用递归还是区间dp，首先都要搞清楚扰乱字符串基础的思想。
有字符串S1，要得到它的扰乱字符串S2，可以将S1拆成【0，i），【i，n）这两段，这两段可以交换位置或者不换，合并在一起得到S1’，对于S1 ’ 合并前的那两段子字符串，对它们两个都可以进行拆分互换或不换的操作，最后得到字符串S2。

但是，有一个隐含却显然的条件需要明确，那就是 对一个字符串进行拆分互换 的操作，之后得到的字符串 仍然是在这块位置、这一段。我发现许多可利用到递归的题目都是如此（最新的一道就是code for 1），在某一段范围内，对该段字符串进行某种操作，又可在这段的子字符串上进行相同操作，在某子字符串上操作不会影响到这段的其他字串段，操作后得到的字串仍落在该子字符串段落内，而且因为是相同操作，操作后得到的字串是该子字符串的扰乱字串，因此只要确定好进行操作的子字符串的位置范围，最终该范围的字串就是该子字符串的扰乱字串。
给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树，因为可以把左右子树当作两棵独立的新树（或许这里的独立的就是我上面那一段想表述的），在这两棵新的树上进行对最初的树相同的操作
或许递归都可以想想二叉树，特判根节点，递归左右子树

如上图所示，假设在S1范围内反复进行拆分互换操作，假设第一次操作将S1区间段 划分为【0，i），【i，n）这两段，由于是冲着得到S1的扰乱字符串去的，接下来的操作就是在这两段上进行以上操作，这一步就有两种走法：

第一种，两个子字符串不互换位置，那么在【0，i）这段上进行上述操作，下一步得到的这段上的字符串就是原来【0，i）位置的扰乱字符串，同样的，【i，n）上操作下一步得到的这段上的字符串是【i，n）的扰乱字符串。
第二种，两个子字符串互换位置，那么在【0，i）这段上进行上述操作，下一步得到的这段上的字符串就是原来【n-i，n）位置的扰乱字符串，同样的，【i，n）上操作下一步得到的这段上的字符串是【0，i）位置的扰乱字符串。

递归写法（TLE）

class Solution {
public:bool isScramble(string s1, string s2) {string sa=s1,sb=s2;sort(sa.begin(),sa.end());sort(sb.begin(),sb.end());if(sa!=sb)return false;//就包括比较了长度 int n=s1.size();if(n==1)return s1==s2;//有点递归出口的意思！不能缺少 for(int i=0;i<=n-1;i++){string s11=s1.substr(0,i);string s12=s1.substr(i,n-i);string s21=s2.substr(0,i);string s22=s2.substr(i,n-i);		if(isScramble(s11,s21)&&isScramble(s12,s22))return true;//长度为i的字段在左边、右边 s21=s2.substr(0,n-i);s22=s2.substr(n-i,i);if(isScramble(s11,s22)&&isScramble(s12,s21))return true;}return false;}
}; 

当然了，上面的划分是 s1划分不交换，s2划分交换
还有s1划分交换，s2划分不交换的，一个交换一个不交换，其实是一种

class Solution {
public:bool isScramble(string s1, string s2) {if(s1 == s2){return true;}string b1 = s1, b2 = s2;sort(b1.begin(), b1.end());sort(b2.begin(), b2.end());if(b1 != b2){return false;}int n = s1.size();for(int i = 1; i <= n - 1; 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, n - i),s2.substr(i)) &&isScramble(s1.substr(n - i), s2.substr(0, i))){return true;}}return false;}
};

区间dp

依旧是根据最上面那段显然的废话
在一段字符串上进行操作，得到的扰乱字符串仍然落在原范围内，也就是长度相同。
动态规划首先想到表示的状态，那就是dp【i】【j】【len】,表示s1字符串中 以i开头长度为len的子字符串与s2字符串中 以j开头长度为len的子字符串 是否互为扰乱字符串

根据以往的经验来说，根字符串有关的题十有八九可以用DP来做，那么难点就在于如何找出状态标识和递推公式。

class Solution {
public:bool isScramble(string s1, string s2) {string sa=s1,sb=s2;sort(sa.begin(),sa.end());sort(sb.begin(),sb.end());if(sa!=sb)return false;//就包括比较了长度 int n=s1.size();if(n==1)return s1==s2;//有点递归出口的意思！不能缺少 vector<vector<vector<bool> > >dp(n,vector<vector<bool> >(n,vector<bool>(n+1,false)));for(int i=0;i<n;i++){for(int j=0;j<n;j++){dp[i][j][1]=(s1[i]==s2[j]);}}
//		从i开始，长度为len，区间终点为i+len-1，i+len-1<=n-1 !!!for(int len=2;len<=n;len++){for(int i=0;i+len<=n;i++){//0123  n=4,n-len-1for(int j=0;j+len<=n;j++){for(int k=1;k<len;k++){//i开始长度为k，[i,i+k-1] if((dp[i][j][k]&&dp[i+k][j+k][len-k])||(dp[i][j+len-k][k]&&dp[i+k][j][len-k])){dp[i][j][len]=true;}
//	注意几个下标界限，k不能取0，i+len要取到n }}}}}
}; 

记忆化递归

class Solution {
public:
//vector<vector<vector<int> > >dp(n,vector<vector<int> >(n,vector<int>(n+1,-1)));bool isScramble(string s1, string s2) {string sa=s1,sb=s2;sort(sa.begin(),sa.end());sort(sb.begin(),sb.end());if(sa!=sb)return false;//就包括比较了长度 int n=s1.size();
//		if(n==1)return s1==s2;//有点递归出口的意思！不能缺少 vector<vector<vector<int> > >dp(n,vector<vector<int> >(n,vector<int>(n+1,-1)));return f(s1,s2,0,0,n,dp);}bool f(string& s1, string& s2,int idx1,int idx2,int len,vector<vector<vector<int> > >& dp){if(dp[idx1][idx2][len]!=-1)return dp[idx1][idx2][len];if(len==0)return true;if(len==1){return dp[idx1][idx2][len]=(s1[idx1]==s2[idx2]);}	for(int k=1;k<=len-1;k++){//两段分界点，前k后n-k if((f(s1,s2,idx1,idx2,k,dp)&&f(s1,s2,idx1+k,idx2+k,len-k,dp))||f(s1,s2,idx1,idx2+len-k,k,dp)&&f(s1,s2,idx1+k,idx2,len-k,dp))return dp[idx1][idx2][len] = 1;
//			注意满足可以return，不满足还要往后看，不能直接return 0 }return dp[idx1][idx2][len]=0;//没有这样的分割点，不是扰乱字符串，返回0，顺便给 dp[idx1][idx2][len]赋值 }
}; 

return dp[idx1][idx2][len]=1,返回1的同时为dp[idx1][idx2][len]顺便赋值为1

记忆化递归到（爆搜+剪枝TLE）

只是加上一条剪枝，就会比简单的递归要强许多
另外，递归思想中以i为分界点，考虑左右两边字符串
此时爆搜，经过了区间dp的形式转变， 考虑，两字符串各自起点相同长度，在递归中占一定优势我猜（奈何测试不了，一个TLE，不给运行时间）
以下代码是直接在记忆化递归的基础上改的
只能说，爆搜是通过递归实现的，而因为是搜索，有可以进行剪枝等等优化（虽然这里加了个剪枝，还是TLE，还是老老实实区间dp、记忆化递归吧，毕竟剪枝不太好找，下面这段的剪枝意义不大，也是TLE）

class Solution {
public:bool isScramble(string s1, string s2) {string sa=s1,sb=s2;sort(sa.begin(),sa.end());sort(sb.begin(),sb.end());if(sa!=sb)return false;//就包括比较了长度 int n=s1.size();return f(s1,s2,0,0,n);}bool f(string& s1, string& s2,int idx1,int idx2,int len){string t1 = s1.substr( idx1, len);string t2 = s2.substr( idx2, len);if ( t1 == t2 ) return true;if(len==0)return true;if(len==1){return (s1[idx1]==s2[idx2]);}	for(int k=1;k<=len-1;k++){//两段分界点，前k后n-k if((f(s1,s2,idx1,idx2,k)&&f(s1,s2,idx1+k,idx2+k,len-k))||f(s1,s2,idx1,idx2+len-k,k)&&f(s1,s2,idx1+k,idx2,len-k))return true;
//			注意满足可以return，不满足还要往后看，不能直接return 0 }return false;}
}; 

参考思路
爆搜+剪枝

参考图