使用下面描述的算法可以擾亂字符串?s?得到字符串?t?：

1. 如果字符串的長度為 1 ，算法停止
2. 如果字符串的長度 > 1 ，執(zhí)行下述步驟：
   • 在一個(gè)隨機(jī)下標(biāo)處將字符串分割成兩個(gè)非空的子字符串。即，如果已知字符串?s?，則可以將其分成兩個(gè)子字符串?x?和?y?，且滿足?s = x + y?。
   • 隨機(jī)?決定是要「交換兩個(gè)子字符串」還是要「保持這兩個(gè)子字符串的順序不變」。即，在執(zhí)行這一步驟之后，s?可能是?s = x + y?或者?s = y + x?。
   • 在?x?和?y?這兩個(gè)子字符串上繼續(xù)從步驟 1 開始遞歸執(zhí)行此算法。

給你兩個(gè)?長度相等?的字符串?s1?和?s2，判斷?s2?是否是?s1?的擾亂字符串。如果是，返回?true?；否則，返回?false?。

思路一：模擬題意

bool check(char *s1,char *s2,int len)
{char ss1[26]={0};char ss2[26]={0};char i=0;for (i=0;i<len;i++){ss1[s1[i]-'a']++;ss2[s2[i]-'a']++;}for(i=0;i<26;i++){if(ss1[i]!=ss2[i]) return false;}return true;
}
char mem[30][30][31];
bool complie(char *s1,char *s2,int len,int s1begin,int s2begin)
{if(mem[s1begin][s2begin][len]==1) return true;if(mem[s1begin][s2begin][len]==2) return false;if(len==0) return true;if(len==1) {mem[s1begin][s2begin][len]=1;return *s1==*s2;}if(!check(s1,s2,len)) {mem[s1begin][s2begin][len]=2;return false;}int i=0;for(i=1;i<len;i++){if(complie(s1,s2,i,s1begin,s2begin) && complie(s1+i,s2+i,len-i,s1begin+i,s2begin+i)) {mem[s1begin][s2begin][len]=1;return true;}if(complie(s1,s2+len-i,i,s1begin,s2begin+len-i) && complie(s1+i,s2,len-i,s1begin+i,s2begin)) {mem[s1begin][s2begin][len]=1;return true;}}mem[s1begin][s2begin][len]=2;return false;
}
bool isScramble(char * s1, char * s2){int len1=0;int len2=0;memset(mem,0,sizeof(mem));while(s1[len1]!=0){len1++;}while(s2[len2]!=0){len2++;}if(len1!=len2) return false;return complie(s1,s2,len1,0,0);
}

分析：

本題擾亂字符串滿足交換兩個(gè)子字符串或保持這兩個(gè)子字符串的順序不變，轉(zhuǎn)換為complie(s1,s2,i,s1begin,s2begin) && complie(s1+i,s2+i,len-i,s1begin+i,s2begin+i)和complie(s1,s2+len-i,i,s1begin,s2begin+len-i) && complie(s1+i,s2,len-i,s1begin+i,s2begin)，通過complie函數(shù)遞歸找到答案，同時(shí)兩個(gè)字符串長度首先要相等，先判斷兩個(gè)字符串長度是否相等再進(jìn)行遞歸返回答案

總結(jié)：

本題考察遞歸的應(yīng)用，利用遞歸交換兩個(gè)子字符串或保持這兩個(gè)子字符串的順序不變判斷是否為擾亂字符串