Why "abbbcbaaccacaacc" is scrambled of "acaaaccabcabcbcb"?


  • 4
    Z

    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"?


  • 0
    S

    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.


  • 0
    F

    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.


  • 0
    W

    @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?


  • 0
    W

    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));
            }
            
        }
    };

  • 12
    M

    ' ' 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
    

Log in to reply
 

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