原题链接在这里：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.
Example 1:
Input:"aabb"
Output:["abba", "baab"]
Example 2:
Input:"abc"
Output:[]
题解：
先判断是否palindrome, 若不是返回空的res.
若是，先判断是否有一个奇数位，若有，改char放中间. 然后两边分别加.
Note: check to find single char after updating the map.
Don't forget to minus its count by 1 after appending it to item.
Time Complexity: O(2^n). n = s.length().
Space: O(n). stack space.
AC Java:
class Solution {
public List<String> generatePalindromes(String s) {
List<String> res = new ArrayList<>();
if(s == null || s.length() == 0){
return res;
}
int [] count = new int[256];
int n = s.length();
int po = -1;
for(int i = 0; i<n; i++){
count[s.charAt(i)]++;
}
int oneCount = 0;
for(int i = 0; i<256; i++){
oneCount += count[i]%2;
if(count[i]%2 == 1){
po = i;
}
}
if(oneCount > 1){
return res;
}
String init = "";
if(po != -1){
init += (char)po;
count[po]--;
}
dfs(count, init, n, res);
return res;
}
private void dfs(int [] count, String cur, int n, List<String> res){
if(cur.length() == n){
res.add(cur);
return;
}
for(int i = 0; i<count.length; i++){
if(count[i] > 0){
count[i] -= 2;
dfs(count, (char)i+cur+(char)i, n, res);
count[i] += 2;
}
}
}
}
与Palindrome Permutation相似.
