267 Palindrome Permutation II

1. Question

Given a strings, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.
For example:
Givens = "aabb", return["abba", "baab"].
Givens = "abc", return[].

2. Implementation

(1) Backtracking
class Solution {
public List<String> generatePalindromes(String s) {
List<String> res = new ArrayList<>();
int[] map = new int[256];
int odd = 0;
for (char c : s.toCharArray()) {
++map[c];
odd += (map[c] & 1) == 1 ? 1 : -1;
}
if (odd > 1) {
return res;
}
String mid = "";
int len = 0;
for (int i = 0; i < 256; i++) {
if (map[i] > 0) {
if ((map[i] & 1) == 1) {
mid = "" + (char)i;
--map[i];
}
map[i] /= 2;
len += map[i];
}
}
getPalindromePermutations("", mid, map, len, res);
return res;
}
public void getPalindromePermutations(String curStr, String mid, int[] map, int len, List<String> res) {
if (curStr.length() == len) {
String revStr = new StringBuilder(curStr).reverse().toString();
res.add(curStr + mid + revStr);
return;
}
for (int i = 0; i < 256; i++) {
if (map[i] > 0) {
--map[i];
getPalindromePermutations(curStr + (char)i, mid, map, len, res);
++map[i];
}
}
}
}

3. Time & Space Complexity

Backtracking: 时间复杂度O((n/2)!), 空间复杂度O(n), 递归的深度最多为n/2