# Why "abbbcbaaccacaacc" is scrambled of "acaaaccabcabcbcb"?

• My method is first divide each of the strings to 2 parts: s11, s12, s21, s22, so that each two of corresponding parts have the same collection of characters i.e. `(sameCollection(s11, s21) && sameCollection(s12, s22)) || (sameCollection(s11, s22) && sameCollection(s12, s21))`. This checks whether the root has been swaped.

However, I can't find a way to divide "abbbcbaaccacaacc" and "acaaaccabcabcbcb" to meet the requirement above, so my result is `false`. But the OJ tells me the expected result is `true`. So can anyone tell me how can "abbbcbaaccacaacc" be scrambled to "acaaaccabcabcbcb"?

• It is a big test case, hardly to present. Could you please update your post with your code? Remember to make comment in it. It is helpful to find the problem.

• from your description, your method is not correct. Since (sameCollection(s11, s21)) implies s11.length() == s21.length() and (sameCollection(s11, s22) implies s11.length() == s22.length(), therefore s21.length() == s11.length() == s22.length(), which cannot guarantee in all cases.

• @forainychen the author trys to divid the two strings using two different method. The s22 in (sameCollection(s11, s21) && sameCollection(s12, s22)) is not same with the one in (sameCollection(s11, s22) && sameCollection(s12, s21)).

I am using the same algorithm and my test case is "hobobyrqd", "hbyorqdbo". I also wonder how this pair could be scrambled?

• My failed code below using the same algorithm( Failed to return true on "hobobyrqd", "hbyorqdbo")
I wonder could there be some wrong test cases? Could anyone give me a way to scramble this test case with binary tree?

``````class Solution {

void divid(string& s1, string& s2, int& div1, int& div2, bool& direction){
int c = 0;
int len = s1.length();
unordered_map<char, int> map;
unordered_map<char,int>::iterator itr;
direction = true;
map[s1[0]]++;
map[s2[0]]--;
if(map[s1[0]] == 0){
div1 = div2 = 1;
return;
}else{
c = 2;
for(int i=1; i<len-1; i++){
itr = map.find(s1[i]);
if(itr == map.end() || itr->second == 0)
c++;
itr = map.find(s2[i]);
if(s1[i] != s2[i] && (itr == map.end() || itr->second == 0))
c++;
map[s1[i]]++;
map[s2[i]]--;
if(map[s1[i]] == 0)
c--;
if(s1[i] != s2[i] && map[s2[i]] == 0)
c--;
if(c==0){
div1 = div2 = i+1;
return;
}
}
}

map.clear();

direction = false;
map[s1[0]]++;
map[s2[len-1]]--;
if(map[s1[0]] == 0){
div1 = 1;
div2 = len-1;
return;
}else{
c = 2;
for(int i=1; i<len-1; i++){
itr = map.find(s1[i]);
if(itr == map.end() || itr->second == 0)
c++;
itr = map.find(s2[len-i-1]);
if(s2[len-i-1] != s1[i] && (itr == map.end() || itr->second == 0))
c++;
map[s1[i]]++;
map[s2[len-i-1]]--;
if(map[s1[i]] == 0)
c--;
if(s2[len-i-1] != s1[i] && map[s2[len-i-1]] == 0)
c--;
if(c==0){
div1 = i+1;
div2 = len - i-1;
return;
}
}
}
div1 = div2 = -1;
}

public:
bool isScramble(string s1, string s2) {
int l1 = s1.length();
int l2 = s2.length();
if(l1 != l2)
return false;
if(l1 == 0 )
return true;
if(l1 == 1)
return s1[0] == s2[0];
int div1, div2;//length of first substr
bool direction;
divid(s1, s2, div1, div2, direction);
if(div1 == -1 || div2 == -1){
return false;
}else {
if(direction)
return isScramble(s1.substr(0,div1), s2.substr(0,div2)) && isScramble(s1.substr(div1), s2.substr(div2));
else
return isScramble(s1.substr(0,div1), s2.substr(div2)) && isScramble(s1.substr(div1), s2.substr(0,div2));
}

}
};``````

• ' ' means split, (a b) means swap

"abbbcbaaccacaacc" can be scrambled to "acaaaccabcabcbcb"

``````         abbbcbaaccacaacc
a | bbbcbaaccacaacc
a | (bbbcbaaccacaac c)
a |       c |      (bbbcbaacc acaac)
a |       c |    acaac      | bbbcbaacc
a |       c |   a caac      | (b bbcbaacc)
a |       c |   a | (c aac) |        bbcbaac  c           | b
a |       c |   a | aac | c |      (bbc baac)         | c | b
a |       c |   a | aac | c |      ba ac    |  (b bc) | c | b
a |       c |   a | aac | c | (b a) | (a c) |  bc | b | c | b
a |       c |   a | aac | c | a | b | c | a |  bc | b | c | b
acaaacabcabcbcb
``````

"hobobyrqd" can be scrambled to "hbyorqdbo"

``````hobobyrqd
h obobyrqd
h | (ob obyrqd)
h |   oby rqd    | (o b)
h | (o by) | rqd | b | o
h | by | o | rqd | b | o
hbyorqdbo
``````

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