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
1
class Solution {
2
public List<String> generatePalindromes(String s) {
3
List<String> res = new ArrayList<>();
4
int[] map = new int[256];
5
int odd = 0;
6
7
for (char c : s.toCharArray()) {
8
++map[c];
9
odd += (map[c] & 1) == 1 ? 1 : -1;
10
}
11
12
if (odd > 1) {
13
return res;
14
}
15
16
String mid = "";
17
int len = 0;
18
19
for (int i = 0; i < 256; i++) {
20
if (map[i] > 0) {
21
if ((map[i] & 1) == 1) {
22
mid = "" + (char)i;
23
--map[i];
24
}
25
map[i] /= 2;
26
len += map[i];
27
}
28
}
29
30
getPalindromePermutations("", mid, map, len, res);
31
return res;
32
}
33
34
public void getPalindromePermutations(String curStr, String mid, int[] map, int len, List<String> res) {
35
if (curStr.length() == len) {
36
String revStr = new StringBuilder(curStr).reverse().toString();
37
res.add(curStr + mid + revStr);
38
return;
39
}
40
41
for (int i = 0; i < 256; i++) {
42
if (map[i] > 0) {
43
--map[i];
44
getPalindromePermutations(curStr + (char)i, mid, map, len, res);
45
++map[i];
46
}
47
}
48
}
49
}
Copied!

3. Time & Space Complexity

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