# [help][recursive-implementation] can any good guy help me find the bug ?

• Input:

``````    "abcd"    "bdac"
``````

Output:

``````     true    Expected:  false
``````

My code is as follows, can anyone explain me where I got wrong ? I just can not found the error !

Code:

``````class Solution {
public:
bool isScramble(string s1, string s2) {
if(s1.size()!=s2.size()) return false;
if(s1==s2)  return true;
string ss1=s1;
string ss2=s2;
sort(ss1.begin(), ss1.end());
sort(ss2.begin(), ss2.end());
if(ss1!=ss2)  return false;
for(int i=1; i<s1.size(); i++){
string l1=s1.substr(0,i), r1=s1.substr(i,s1.size()-i);
string l2=s2.substr(0,i), r2=s2.substr(i,s2.size()-i);
string _l2=s2.substr(s2.size()-i,i), _r2=s2.substr(0, s2.size()-i);
if(isScramble(l1, l2) && isScramble(r1, r2))
return true;
if(isScramble(l1, _l2) && isScramble(r1,_r2));
return true;
}
return false;
}
};``````

• This method can also easily cause the TLE problem

• Dynamic solutioclass Solution

``````class Solution {
public:
bool isScramble(string s1, string s2) {
/**
*  dp[k][i][j] means s1[i,i+k-1]   s2[j,j+k-1]   k is the length
*  dp[1][i][j]=(s1[i]==s2[j])
*
*  dp[k][i][j] =
*       dp[divk][i][j] && dp[k-divk][i+divk][j+divk] ||
*       dp[divk][i][j+k-divk] && dp[k-div][i+div][j]
*    divk : mean split the k to two parts, so divk is in (0, k)
**/
int len1=s1.size(), len2=s2.size();
if(len1!=len2)  return false;
if(s1==s2)  return true;
/*** dp[len1+1][len1][len1] **/
vector<vector<vector<bool>>> dp(len1+1, vector<vector<bool>>(len1, vector<bool>(len1)));

for(int i=0; i<len1; i++){
for(int j=0; j<len1; j++){
dp[1][i][j]=s1[i]==s2[j];
}
}

for(int k=2; k<=len1; k++){
for(int i=0; i<len1-k+1; i++){
for(int j=0; j<len1-k+1; j++){
dp[k][i][j]=false;
for(int divk=1; divk<k && dp[k][i][j]==false; divk++){
dp[k][i][j]=(dp[divk][i][j] && dp[k-divk][i+divk][j+divk]) ||
(dp[divk][i][j+k-divk] && dp[k-divk][i+divk][j]);
}
}
}
}
return dp[len1][0][0];
}
};``````

• ``````class Solution {
public:
bool isScramble(string s1, string s2) {
if(s1 == s2)  return true;
int size_s1 = s1.size(), size_s2 = s2.size();
if(size_s1 != size_s2)  return false;
string ss1(s1), ss2(s2);
/** the sorting cut edge is necessary **/
sort(ss1.begin(), ss1.end());
sort(ss2.begin(), ss2.end());
if(ss1 != ss2)  return false;
for(int i = 1; i < size_s1; i++) {
string s1_sub = s1.substr(0, i);
string s2_sub = s2.substr(0, i);
if( (isScramble(s1.substr(0, i), s2.substr(0, i)) && isScramble(s1.substr(i), s2.substr(i)))
||  (isScramble(s1.substr(0, i), s2.substr(size_s1 - i, i)) && isScramble(s1.substr(i), s2.substr(0, size_s1 - i))) )
return true;
}
return false;
}
};**strong text**``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.