[LeetCode] Palindrome Permutation I & II

 1 class Solution {
 2 public:
 3     bool canPermutePalindrome(string s) {
 4         vector<int> cnt(256, 0);
 5         for (auto a : s) ++cnt[a];
 6         bool flag = false;
 7         for (auto n : cnt) if (n & 1) {
 8             if (!flag) flag = true;
 9             else return false;
10         }
11         return true;
12     }
13 };

 1 class Solution {
 2 public:
 3     void dfs(vector<string> &res, vector<int> &cnt, string &s, int l, int r) {
 4         if (l >= r) {
 5             res.push_back(s);
 6             return;
 7         }
 8         for (int i = 0; i < cnt.size(); ++i) if (cnt[i] >= 2) {
 9             cnt[i] -= 2;
10             s[l] = s[r] = i;
11             dfs(res, cnt, s, l + 1, r - 1);
12             cnt[i] += 2;
13         }
14     }
15     vector<string> generatePalindromes(string s) {
16         vector<int> cnt(256, 0);
17         for (auto a : s) ++cnt[a];
18         bool flag = false;
19         for (int i = 0; i < cnt.size(); ++i) if (cnt[i] & 1) {
20             if (!flag) {
21                 flag = true;
22                 s[s.length() / 2] = i;
23             } else {
24                 return {};
25             }
26         }
27         vector<string> res;
28         dfs(res, cnt, s, 0, s.length() - 1);
29         return res;
30     }
31 };