# Palindrome Permutation II

• ``````class Solution(object):
def permutePalindromesDetail(self, compressed, odd_char, result, tmp):
if not compressed:
palindrome = ''.join(tmp+[odd_char]+tmp[::-1])
result.append(palindrome)
return
pre = ''
for i in range(len(compressed)):
if pre != compressed[i]:
tmp.append(compressed[i])
self.permutePalindromesDetail(compressed[:i]+compressed[i+1:], odd_char, result, tmp)
tmp.pop()
pre = compressed[i]

def generatePalindromes(self, s):
word_count = collections.Counter(s)
odd_char, odd_elements, compressed, result = '', 0, [], []
for k,v in word_count.items():
if v % 2 == 1:
odd_elements += 1
odd_char = k
for _ in range(v / 2):
compressed.append(k)
if odd_elements > 1:
return []

result = []
tmp = []
compressed.sort()
self.permutePalindromesDetail(compressed, odd_char, result, tmp)
return result
``````

• My easy Java solution

``````class Solution {
public List<String> generatePalindromes(String s) {
List<String> res = new ArrayList<>();
int[] table = new int[128];
int cnt = 0;
for(int i=0;i<s.length();i++){
table[s.charAt(i)]++;
cnt = (table[s.charAt(i)] % 2 == 0) ? cnt - 1 : cnt + 1;
}
if(s.equals("") || cnt > 1){
return res;
}
String temp = "";
for(int i=0;i<128 && cnt == 1;i++){
if(table[i] % 2 == 1){
temp += (char) i;
break;
}
}
backtrackHelper(table,temp,res,s.length());

return res;
}

public void backtrackHelper(int[] table,String curr,List<String> res,int l){
if(curr.length() == l){
return;
}
for(int i=0;i<128;i++){
if(table[i] > 1){
table[i] -= 2;
char c = (char) i;
String temp = c + curr + c;
backtrackHelper(table,temp,res,l);
table[i] += 2;
}
}
}
}
``````

• Since the `Set < String > set = new HashSet < > ();` need to store all the permutation before return, so Space Complexity is at most O((n/2+1)!), which is the same as time complexity, right?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.