Palindromic Permutations

1.Given a string, determine if a permutation of the string could form a palindrome.

(use the thing like the hash map)

bool canPermutePalindrome(string s) {
        int dict[128]={0};
        for(auto c:s){
            dict[c]++;
        }
        int odd=0;
        for(int i=0;i<128;i++){
            if(dict[i]%2!=0){
                odd++;
                if(odd>1) return false;
            }
        }
        return true;
    }

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

First, we have to check that if this string s can form palindrome or not, that is the problem1.

Second, divide the string into half, like aabb to ab and ab, or aabbccd to abc and abc and d.

Third, get the all permutation of the half string, like ab has ab and ba.

Fourth, append reverse half to the original half, if there is odd one, put it in the middle, like ab+ba or, abc+d+cba.

class Solution {
public:
    vector<string> generatePalindromes(string s) {
        vector<string> candidates;
        unordered_map<char,int> dict;
        for(auto c:s){
            dict[c]++;
        }
        int odd=0; string half; char mid;
        for(auto p:dict){
            if(p.second%2!=0){
                odd++;
                mid = p.first;
                if(odd>1) return candidates;
            }
            half+=string (p.second/2, p.first);
        }
        candidates=all_permutation(half);
        for (auto &candidate:candidates){
            string t(candidate);
            reverse(t.begin(),t.end());
            if(odd) t=mid+t;
            candidate+=t;
        }
        return candidates;
    }
private:
    vector<string> all_permutation(string s){
        vector<string> ret;
        string t=s;
        do{
            ret.push_back(t);
            next_permutation(t.begin(), t.end()); 
        }while(t!=s);
        return ret;
    }
};