[leetcode] 267. Palindrome Permutation II解題レポート

タイトルリンク:https://leetcode.com/problems/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  [] .
構想:所与の文字列中の各文字の個数を統計し、1つ以上の単数の文字がある場合、説明は回文を構成できないので、このとき[]を返す. 
単数文字が1つしかない場合や単数文字がない場合は、偶数回出現する文字を半分に分けて全配列に用い、1回の文数に組み合わせる.全配列文字列+単数回出現文字+全配列文字列反転となる.
コードは次のとおりです.

class Solution {
public:
    vector<string> generatePalindromes(string s) {
        unordered_map<char, int> hash;
        string a = "", str = "";
        int num = 0;
        for(auto ch: s) hash[ch]++;
        for(auto val: hash)
        {
            if(val.second%2==1){a = val.first; num++;}
            for(int i = 0; i < val.second/2; i++)
                str += val.first;
        }
        if(num > 1) return result;
        sort(str.begin(), str.end());
        string pre = str;
        do{
            string tem = str, ans;
            reverse(tem.begin(), tem.end());
            result.push_back(str + a + tem);
            next_permutation(str.begin(), str.end());
        }while(str != pre);
        return result;
    }
private:
    vector<string> result;
};