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 [].

Hint:

1. If a palindromic permutation exists, we just need to generate the first half of the string.
2. To generate all distinct permutations of a (half of) string, use a similar approach from:  or .

的拓展，266只是判断全排列是否存在回文的，此题要返回所有的回文全排列。提示：如果回文全排列存在，只需要生成前半段字符串，后面的直接根据前半段得到。用Permutations II or Next Permutation的方法去生成不同的全排列。

Python:

class Solution(object):    def generatePalindromes(self, s):        """        :type s: str        :rtype: List[str]        """        cnt = collections.Counter(s)        mid = ''.join(k for k, v in cnt.iteritems() if v % 2)        chars = ''.join(k * (v / 2) for k, v in cnt.iteritems())        return self.permuteUnique(mid, chars) if len(mid) < 2 else []        def permuteUnique(self, mid, nums):        result = []        used = [False] * len(nums)        self.permuteUniqueRecu(mid, result, used, [], nums)        return result        def permuteUniqueRecu(self, mid, result, used, cur, nums):        if len(cur) == len(nums):            half_palindrome = ''.join(cur)            result.append(half_palindrome + mid + half_palindrome[::-1])            return        for i in xrange(len(nums)):            if not used[i] and not (i > 0 and nums[i-1] == nums[i] and used[i-1]):                used[i] = True                cur.append(nums[i])                self.permuteUniqueRecu(mid, result, used, cur, nums)                cur.pop()                used[i] = False

Python:

class Solution2(object):    def generatePalindromes(self, s):        """        :type s: str        :rtype: List[str]        """        cnt = collections.Counter(s)        mid = tuple(k for k, v in cnt.iteritems() if v % 2)        chars = ''.join(k * (v / 2) for k, v in cnt.iteritems())        return [''.join(half_palindrome + mid + half_palindrome[::-1]) \                for half_palindrome in set(itertools.permutations(chars))] if len(mid) < 2 else []

C++:

class Solution {public:    vector
     
       generatePalindromes(string s) {        vector
      
        res;        unordered_map
       
         m;        string t = "", mid = "";        for (auto a : s) ++m[a];        for (auto it : m) {            if (it.second % 2 == 1) mid += it.first;            t += string(it.second / 2, it.first);            if (mid.size() > 1) return {};        }        permute(t, 0, mid, res);        return res;    }    void permute(string &t, int start, string mid, vector
        
          &res) {        if (start >= t.size()) {            res.push_back(t + mid + string(t.rbegin(), t.rend()));        }         for (int i = start; i < t.size(); ++i) {            if (i != start && t[i] == t[start]) continue;            swap(t[i], t[start]);            permute(t, start + 1, mid, res);            swap(t[i], t[start]);        }    }};
        
       
      
     

C++:

class Solution {public:    vector
     
       generatePalindromes(string s) {        vector
      
        res;        unordered_map
       
         m;        string t = "", mid = "";        for (auto a : s) ++m[a];        for (auto &it : m) {            if (it.second % 2 == 1) mid += it.first;            it.second /= 2;            t += string(it.second, it.first);            if (mid.size() > 1) return {};        }        permute(t, m, mid, "", res);        return res;    }    void permute(string &t, unordered_map
        
          &m, string mid, string out, vector
         
           &res) {        if (out.size() >= t.size()) {            res.push_back(out + mid + string(out.rbegin(), out.rend()));            return;        }         for (auto &it : m) {            if (it.second > 0) {                --it.second;                permute(t, m, mid, out + it.first, res);                ++it.second;            }        }    }};
         
        
       
      
     

C++:

class Solution {public:    vector
     
       generatePalindromes(string s) {        vector
      
        res;        unordered_map
       
         m;        string t = "", mid = "";        for (auto a : s) ++m[a];        for (auto it : m) {            if (it.second % 2 == 1) mid += it.first;            t += string(it.second / 2, it.first);            if (mid.size() > 1) return {};        }        sort(t.begin(), t.end());        do {            res.push_back(t + mid + string(t.rbegin(), t.rend()));        } while (next_permutation(t.begin(), t.end()));        return res;    }};
       
      
     

　　

类似题目：