266.Palindrome Permutation
https://www.cnblogs.com/grandyang/p/5223238.html
判断一个字符串的全排列能否形成一个回文串。
能组成回文串,在字符串长度为偶数的情况下,每个字符必须成对出现;奇数的情况下允许一个字符单独出现,其他字符都必须成对出现。用一个set对相同字符进行加减即可。
class Solution {
public:
/**
* @param s: the given string
* @return: if a permutation of the string could form a palindrome
*/
bool canPermutePalindrome(string &s) {
// write your code here
unordered_set<char> container;
for(auto c : s){
if(container.find(c) != container.end())
container.erase(c);
else
container.insert(c);
}
return container.empty() || container.size() == ;
}
};
267.Palindrome Permutation II
https://www.cnblogs.com/grandyang/p/5315227.html
class Solution {
public:
/**
* @param s: the given string
* @return: all the palindromic permutations (without duplicates) of it
*/
vector<string> generatePalindromes(string &s) {
// write your code here
vector<string> res;
string mid = "";
int number = ;
unordered_map<char,int> m;
for(auto c : s)
m[c]++;
for(auto& it : m){
if(it.second % == )
mid += it.first;
it.second /= ;
number += it.second;
if(mid.size() > )
return res;
}
generatePalindromes(m,number,res,mid,"");
return res;
}
void generatePalindromes(unordered_map<char,int> m,int number,vector<string>& res,string mid,string out){
if(out.size() == number){
res.push_back(out + mid + string(out.rbegin(),out.rend()));
return;
}
for(auto& it : m){
if(it.second > ){
it.second--;
generatePalindromes(m,number,res,mid,out + it.first);
it.second++;
}
}
}
};