string cur, using cur.push_back(cur[i]) will add an empty space inbetween.


  • 0
    J

    So my questions lies in my gen_helper function. For eg, "aabb", I will first find all the permutation for "ab", so cur="ab", then I reversely add letters from cur. It is supposed to be "abba", but my solution will give "ab" "ba" instead. Could someone tell me anything wrong with my code?

    class Solution {
    public:
    vector<string> generatePalindromes(string s) {
       vector<string> res;
        if(s.empty())
            return res;
        if(s.size()==1){
            res.push_back(s);
            return res;
        }
        sort(s.begin(), s.end());
        unordered_map<char, int> smap;
        int count=1;
        for(int i=1; i<s.size(); i++){
            if(s[i-1]==s[i]){
                count++;
            }else{
                smap.insert({s[i-1], count});
                count=1;
            }
        }
        smap.insert({s[s.size()-1], count});
        
     
    
    ///to print out smap
    for ( auto it = smap.begin(); it != smap.end(); ++it )
      std::cout << " " << it->first << ":" << it->second;
    std::cout << std::endl;
    
    pair<bool, char> s_pair=pos_panlindrome(smap);
        if(!s_pair.first)
            return res;
    
        std::cout<<"after changing the smap"<<endl;
        ///to print out smap
        for ( auto it = smap.begin(); it != smap.end(); ++it )
            std::cout << " " << it->first << ":" << it->second;
        std::cout << std::endl;
    
        
        //use backtrack to create the strings
        string cur;
        int total =s.size()/2;
        gen_helper(smap, res, cur, s_pair.second, 0, total);
        return res;
    

    }

     void gen_helper(unordered_map<char, int>& smap, vector<string> &res, string cur, char pos, int count, int total){
       if(count>=total){
            int half_size=cur.size();
            cout<<"half_size is"<<half_size;
            if(pos!='1'){// add that one odd character
                cur.push_back(pos);
                cout<<pos;
            }
            for(int i=half_size; i>=0; i--){
                cur.push_back(cur[i]);
                //cout<<cur<<endl;
            }
            
            res.push_back(cur);
            for (std::vector<string>::const_iterator i = res.begin(); i != res.end(); ++i)
                std::cout << *i << ' ';
    
            return;
        }
        for(auto& m:smap){
            if(m.second==0)
                continue;  //as the case 
            cur.push_back(m.first);
            m.second --;
            gen_helper(smap, res, cur, pos, count+1, total);
            cur.pop_back();
            m.second ++;
        }
    }
    
    //return true if there is possible to have a panlindorm.
    //return false if not possible.
    pair<bool, char> pos_panlindrome(unordered_map<char, int>& smap){
        int flag=0;
        char pos='1';
        bool ans=true;
        for(auto& m : smap){
            if(m.second%2==1){
                flag++;
                pos=m.first;
                if(flag>=2){
                    ans=false;
                    pair<bool, char> foo;
                    foo = std::make_pair(ans, pos);
                    return foo;
                }
            }
            m.second /= 2;
        }
        pair<bool, char> boo;
        boo=make_pair(ans, pos);
        return boo;
    }
    

    };'''

    Here are the result showing as:
    Run Code Result:×

    Your input
    "aabb"

    Your stdout
    b:2 a:2
    after changing the smap
    b:1 a:1
    half_size is2baab half_size is2baab abba

    Your answer
    ["ba","ab"]

    Expected answer
    ["abba","baab"]


Log in to reply
 

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