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
class Solution {
public:
bool canPermutePalindrome(string s) {
vector<int> cnt(, );
for (auto a : s) ++cnt[a];
bool flag = false;
for (auto n : cnt) if (n & ) {
if (!flag) flag = true;
else return false;
}
return true;
}
};
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.
没按提示来，直接用的DFS，不知道符不符合要求。
class Solution {
public:
void dfs(vector<string> &res, vector<int> &cnt, string &s, int l, int r) {
if (l >= r) {
res.push_back(s);
return;
}
for (int i = ; i < cnt.size(); ++i) if (cnt[i] >= ) {
cnt[i] -= ;
s[l] = s[r] = i;
dfs(res, cnt, s, l + , r - );
cnt[i] += ;
}
}
vector<string> generatePalindromes(string s) {
vector<int> cnt(, );
for (auto a : s) ++cnt[a];
bool flag = false;
for (int i = ; i < cnt.size(); ++i) if (cnt[i] & ) {
if (!flag) {
flag = true;
s[s.length() / ] = i;
} else {
return {};
}
}
vector<string> res;
dfs(res, cnt, s, , s.length() - );
return res;
}
};