267. 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.

Example 1:

Input: "aabb"
Output: ["abba", "baab"]

Example 2:

Input: "abc"
Output: []

A:

每次从一个seed开始， 左右两边加上可能的值。

然后dfs直到都用光。

class Solution {
public:
    vector<string> generatePalindromes(string s) {
        if(s.length() == 0)
            return vector<string>();        
        unordered_map<char,int> M;
        for(auto c:s)
            M[c]++;
        int oddCount = 0;
        char oddCh = '0';
        for(auto iter=M.begin(); iter!=M.end(); iter++){
            if(iter->second %2){
                oddCount++;
                oddCh = iter->first;
            }
        }
        if(oddCount>=2)
            return vector<string>();
        string seed="";
        if(oddCount){
            seed += oddCh;
            M[oddCh]--;
            if(M[oddCh]==0){
                M.erase(oddCh);
            }
        }
        vector<string> res;
        dfs(seed, M,res);
        return res;
    }
private:
    void dfs(string &seed, unordered_map<char,int> &M, vector<string> & res){
        if(M.empty()){
            res.push_back(seed);
            return;
        }
        vector<char> chars; // save a copy, so that we dould not modify on M directly while looping it
        for(auto iter=M.begin();iter!= M.end();iter++){
            chars.push_back(iter->first);
        }
        for(auto ch : chars){
            string tmp(1,ch);
            string newSeed = tmp+ seed + tmp;
            M[ch]-=2;
            if(M[ch]==0)
                M.erase(ch);
            dfs(newSeed, M, res);
            M[ch]+=2; // put them back
        }
    }
};

Mistakes: