My C++ Solution


  • 0
    P
    class Solution {
    public:
        vector<string> generatePalindromes(string s) {
            vector<string> res;
            if(s.empty())
                return res;
                
            if(!canGeneratePalin(s))
                return res;
            
            unordered_map<char, int> table;
            for(auto& c : s)
                if(table.find(c) == table.end())
                    table[c] = 1;
                else
                    table[c]++;
    
            char sp;
            for(auto& c : s)
                if(table[c] % 2 == 1)
                    sp = c;
                    
            string tmp;
            DFS(res, table, tmp, 0, s, sp);
            return res;
        }
    
        void DFS(vector<string>& res,unordered_map<char, int>& table, string& tmp, int count, string s, char sp){
            if(count == s.size()/2){
                string tp = tmp;
                reverse(tp.begin(), tp.end());
                if(sp != 0x00)
                    res.push_back(tmp + sp + tp);
                else
                    res.push_back(tmp + tp);
                return;
            }
            
            for(auto& iter : table)
                if(iter.second > 1){
                    tmp += iter.first;
                    iter.second -= 2;
                    DFS(res, table, tmp, count + 1, s, sp);
                    tmp = tmp.substr(0, tmp.size() - 1);
                    iter.second += 2;
                }
                
        }
    private:
        bool canGeneratePalin(string str){
            bitset<256> tbl;
            for(auto& c : str)
                tbl.flip(c);
            return tbl.count() < 2;
        }
    };
    

Log in to reply
 

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