面试题 01.04. 回文排列

面试题 01.04. 回文排列 - 力扣（LeetCode）

如果是某个回文串的排列之一，那么：所有字母个数均为偶数或者仅有一个字母个数为奇数（放在回文序列中间）。

class Solution {
public:
    bool canPermutePalindrome(string s) {
        int count[128] = {0};
        for(const auto &c : s){//加1减1，不用累加数量
            if(count[c] == 1)   --count[c];
            else ++count[c];
        }
        int val = accumulate(count, count+128, 0);
        return val == 0 || val == 1;
    }
};

节省空间可以使用bitset：

class Solution {
public:
    bool canPermutePalindrome(string s) {
        bitset<128> flag;
        for(const auto &c : s){
            if(flag[c] == 1)   flag[c] = 0;//消除
            else flag[c] = 1;
        }
        return flag.count() < 2;
    }
};

可以使用函数bitset.flip()翻转：

class Solution {
public:
    bool canPermutePalindrome(string s) {
        bitset<128> flag;
        for(const auto &c : s)  flag[c].flip();
        return flag.count() < 2;
    }
};