LeetCode刷题实战267：回文排列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.
示例
输入: "aabb"
输出: ["abba", "baab"]
示例 2：
输入: "abc"
输出: []
解题
class Solution {
vector<string> ans;
int n;
public:
vector<string> generatePalindromes(string s) {
vector<int> count(128,0);
n = s.size();
for(char ch : s)
count[ch]++;
int odd = 0, idx;
for(int i = 0; i < 128; ++i)
{
if(count[i]&1)
{
odd++;
idx = i;
}
if(odd > 1)
return {};
}
s = odd ? string(1, idx) : "";
odd ? count[idx]-- : 0;//奇数的字符-1
dfs(count,s);
return ans;
}
void dfs(vector<int>& count, string s)
{
if(s.size()==n)
{
ans.push_back(s);//长度够了返回
return;
}
for(int i = 0; i < 128; ++i)
{
if(count[i])
{
count[i] -= 2;//两侧加上相同字符，还是回文
dfs(count, char(i)+s+char(i));
count[i] += 2;//回溯
}
}
}
};