Palindrome Permutation II

Given a string s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.

For example:

Given s = "aabb", return ["abba", "baab"].

Given s = "abc", return [].

First, count the frequency of the each character in the string. If there are more than 1 characters whose frequency is odd, it can’t form a palindrome by permutation.

Second, use DFS to construct the palindrome.

class Solution {
public:
    vector<string> generatePalindromes(string s) {
        vector<string> ans;
        string ps;
        unordered_map<char, int> map;
        for(size_t i = 0; i < s.size(); i++){
            if(map.find(s[i]) == map.end()){
                map[s[i]] = 1;
            }
            else{
                map[s[i]]++;
            }
        }
        int count = 0;
        char c;
        for(auto it = map.begin(); it != map.end(); it++){
            if(it->second % 2 == 1){
                count++;
                c = it->first;
            }
        }
        if(count > 1) return ans;//can not form a palindrome
        
        if(count == 1){
            ps.push_back(c);//center of the palindrome string
            map[c]--;
        }
        
        DFS(map, ps, ans);
        return ans;
    }
    
    void DFS(unordered_map<char, int> map, string s, vector<string> & ans){
        int isEnd = true;
        for(auto it = map.begin(); it != map.end(); it++){
            if(it->second > 0) isEnd = false;
        }
        if(isEnd == true){
            ans.push_back(s);
            return ;
        }
        
        //non leaf node of tree
        for(auto it = map.begin(); it != map.end(); it++){
            if(it->second > 0){
                it->second -= 2;
                s.insert(0, 1, it->first);
                s.push_back(it->first);
                DFS(map, s, ans);
                s.erase(0,1);
                s.pop_back();
                it->second += 2;
            }
        }
    }
};