题目：

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 .

链接： 

题解：

求一个字符串能生成的all palindromic permutaitons。这个题目又写得很长。 总的来说我们要考虑以下一些点:

1. 给定s是否能生成Palindrome
2. 生成的Palindrome的奇偶性，是奇数的话中间的字符是哪一个
3. 利用permutation II的原理，计算左半部string
4. 根据Palindrome的奇偶性判断是否要加上中间的独立字符
5. 根据计算出的左半部string，计算右半部string，合并，加入到结果集中
6. 复杂度的计算(留给二刷了)

Time Complexity - O(2ⁿ)， Space Complexity - O(2ⁿ)

public class Solution {    private boolean isOddPalindrome;    private String singleChar;        public List
     
       generatePalindromes(String s) {        List
      
        res = new ArrayList<>();        String evenPalindromeString = generateEvenPalindromeString(s);        if(evenPalindromeString.length() == 0) {            if(this.isOddPalindrome)                res.add(singleChar);            return res;        }                char[] arr = evenPalindromeString.toCharArray();        Arrays.sort(arr);                StringBuilder sb = new StringBuilder();        boolean[] visited = new boolean[arr.length];        generatePalindromes(res, sb, arr, visited);        return res;    }        private void generatePalindromes(List
       
         res, StringBuilder sb, char[] arr, boolean[] visited) {        if(sb.length() == arr.length) {  // we only get permutation of left part of the result palindrome            String s = sb.toString();            res.add(this.isOddPalindrome ? (s + this.singleChar + reverse(s)) : (s + reverse(s)) );            return;        }                for(int i = 0; i < arr.length; i++) {            if(visited[i] || (i > 0 && arr[i] == arr[i - 1] && !visited[i - 1])) {      //skip duplicate                continue;            }            if(!visited[i]) {                visited[i] = true;                sb.append(arr[i]);                generatePalindromes(res, sb, arr, visited);                sb.setLength(sb.length() - 1);                visited[i] = false;            }        }    }        private String reverse(String s) {              //reverse string        char[] arr = s.toCharArray();        int lo = 0, hi = s.length() - 1;        while(lo < hi) {            char c = arr[lo];            arr[lo++] = arr[hi];            arr[hi--] = c;        }        return String.valueOf(arr);    }        private String generateEvenPalindromeString(String s) {         // get even chars of palindrome        Set
        
          set = new HashSet<>();        StringBuilder sb = new StringBuilder();        for(int i = 0; i < s.length(); i++) {            char c = s.charAt(i);            if(set.contains(c)) {                set.remove(c);                sb.append(c);               // append only even counted chars            } else {                set.add(c);            }        }                if(set.size() <= 1) {            if(set.size() == 1) {                for(char chr : set) {                    this.singleChar = String.valueOf(chr);                }                this.isOddPalindrome = true;            }            return sb.toString();        } else {            return "";        }    }}
        
       
      
     

 

Reference:

https://leetcode.com/discuss/53626/ac-java-solution-with-explanation