# [leetcode] Palindrome Permutation II

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

First, count the frequency of the each character in the string. If there are more than 1 characters whose frequency is odd, it can’t form a palindrome by permutation.

Second, use DFS to construct the palindrome.

```class Solution {
public:
vector<string> generatePalindromes(string s) {
vector<string> ans;
string ps;
unordered_map<char, int> map;
for(size_t i = 0; i < s.size(); i++){
if(map.find(s[i]) == map.end()){
map[s[i]] = 1;
}
else{
map[s[i]]++;
}
}
int count = 0;
char c;
for(auto it = map.begin(); it != map.end(); it++){
if(it->second % 2 == 1){
count++;
c = it->first;
}
}
if(count > 1) return ans;//can not form a palindrome

if(count == 1){
ps.push_back(c);//center of the palindrome string
map[c]--;
}

DFS(map, ps, ans);
return ans;
}

void DFS(unordered_map<char, int> map, string s, vector<string> & ans){
int isEnd = true;
for(auto it = map.begin(); it != map.end(); it++){
if(it->second > 0) isEnd = false;
}
if(isEnd == true){
ans.push_back(s);
return ;
}

//non leaf node of tree
for(auto it = map.begin(); it != map.end(); it++){
if(it->second > 0){
it->second -= 2;
s.insert(0, 1, it->first);
s.push_back(it->first);
DFS(map, s, ans);
s.erase(0,1);
s.pop_back();
it->second += 2;
}
}
}
};
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.