# 267 Palindrome Permutation II

## 1. Question

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

## 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();
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

Last updated