解法一：哈希

1、思路

考虑一个字符串是否能够组成回文，只有两种情况：

• 所有不同字符都出现偶数次；
• 只有一个字符出现奇数次，其余字符出现偶数次。

假设字符集为ASCII，先统计每个字符出现的次数，再遍历查找出现奇数次字符的个数，若个数大于1，则该字符串不能组成回文。

2、代码

class Solution {
public:
    bool canPermutePalindrome(string s) {
        vector<int> hash(128, 0);           //数组模拟哈希

        for (char& ch : s)
        {
            hash[ch] ++ ;
        }

        int countOdd = 0;
        for (auto& i : hash)
        {
            if (i % 2 == 1) countOdd ++ ;   //计算出现奇数次字符的个数
        }

        return countOdd <= 1;
    }
};

解法二：位运算

1、思路

思路同上，只不过用位运算来取代了哈希表，介绍了C++中bitset的简单用法。

2、代码

class Solution {
public:
    bool canPermutePalindrome(string s) {
        bitset<128> bitVector;      //声明128位长的比特位

        for (char& ch : s)
        {
            bitVector.flip(ch);     //flip用来把bitVector中ch处的二进制位取反
        }

        //最后判断bitVector是否为空，或者只存在一个二进制位为1的位
        return bitVector.none() || bitVector.count() == 1;
    }
};