leetcode 266.Palindrome Permutation 、267.Palindrome Permutation II

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++;
}
}
}
};
上一篇:[LeetCode] 267. Palindrome Permutation II 回文全排列 II


下一篇:hdu 1053 (huffman coding, greedy algorithm, std::partition, std::priority_queue ) 分类: hdoj 2015-06-18 19:11 22人阅读 评论(0) 收藏