Palindrome Permutation I
Given a string, determine if a permutation of the string could form a palindrome.
For example,"code" -> False, "aab" -> True, "carerac" -> True.
Hint:
- Consider the palindromes of odd vs even length. What difference do you notice?
- Count the frequency of each character.
- If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times
分析：
这个问题不需要判断是否是回文字符串，而是判断是否能组成回文字符串，换句话说就是字母在原字符串中的顺序无关。
解法：
可根据回文定义得出，即允许出现奇数次的字母种数最多为1
证明：
充分性，将出现奇数次的字母放在中间，若无出现奇数次的字母，则直接做下一步，然后从中间向两边依次放置出现偶数次的字母，满足；
必要性，任意回文字符串都满足中轴对称，偶数个字母则有出现奇数次的字母种数为0，奇数个字母则有出现奇数次的字母种数为1，满足；
代码：
bool isPermutation(string str){
vector<char> bin( ,);
for(char c : str)
bin[int(c - 'a')] ^= ;
int count = ;
for(int i : bin)
count += i;
return count <= ;
}
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 [].
Hint:
- If a palindromic permutation exists, we just need to generate the first half of the string.
- To generate all distinct permutations of a (half of) string, use a similar approach from: Permutations II or Next Permutation.
分析：
这个问题相比上个问题，是个后续输出工作，直接排列所有情况即可，证明比较直观。
解法：
直接排列。小技巧同Hint. 1给出的，只需要得出一边的排列。
代码：
void dfs(unordered_set<string> &uset, string str, vector<int> bin, int total) {
if(total == ) {
uset.insert(str);
return;
}
for(int i = ; i < bin.size(); i++) {
if(bin[i] == )
continue;
bin[i]--;
dfs(uset, str + char(i + 'a'), bin, total - );
bin[i]++;
}
return;
}
vector<string> permutation(string str){
vector<int> bin( ,);
for(char c : str)
bin[int(c - 'a')]++;
int count = , total = ;
char record;
for(int i = ; i < bin.size(); i++) {
total += bin[i];
if((bin[i] & ) == ) {
record = char(i + 'a');
count++;
}
}
vector<string> vs;
if(count > )
return vs;
for(int &i : bin)
i /= ;
unordered_set<string> uset;
dfs(uset, "", bin, total / );
for(string s : uset) {
string str = s;
if(count == )
str += record;
reverse(s.begin(), s.end());
str += s;
vs.push_back(str);
}
return vs;
}