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.
For example:
Given s = "aabb", return ["abba", "baab"].
Given s = "abc", return [].
public List<String> generatePalindromes(String s) {
List<String> res = new ArrayList();
if(s.length() == 0) return res;
int odd = 0;
Map<Character, Integer> map = new HashMap();
for(char c : s.toCharArray()){
int num = map.getOrDefault(c, 0);
map.put(c, ++ num);
odd ++;
if((num & 1) == 0) odd -= 2;
}
if(odd > 1) return res;
Set <String> set = new HashSet();
Helper(set, map, "",s.length());
res.addAll(set);
return res;
}
private void Helper(Set <String> res, Map<Character, Integer> map, String tmp, int len){
if(tmp.length() > 0 && (len & 1) == 0 && tmp.length() == len >> 1){
res.add(tmp + new StringBuilder(tmp).reverse().toString());
return ;
}
Iterator it = map.entrySet().iterator();
while (it.hasNext()) {
Map.Entry pair = (Map.Entry)it.next();
char c = (char) pair.getKey();
int num = (int) pair.getValue();
if(num == 1 && tmp.length() * 2 + 1 == len){
res.add(tmp + String.valueOf(c) + new StringBuilder(tmp).reverse().toString());
return;
}
int curr_num = num;
while(curr_num >= 2){
curr_num -= 2;
map.put(c, curr_num);
Helper(res, map, tmp + String.valueOf(c), len);
}
map.put(c, num);
}
}