题目来源

• leetcode：266-VIP. 回文全排列

题目描述

给定一个字符串，判断该字符串中是否可以通过重新排列组合，形成一个回文字符串。

题目解析

思路

回文序列：

• 如果字符串的长度是奇数长度时，只有一个字母出现的次数是奇数，其余均为偶数
• 如果字符串的长度是奇偶长度时，每个字母出现的次数一定是偶数次

实现

同一个map来统计

class Solution {
    
public:
    bool canPermutePalindrome(string s) {
    
        unordered_map<char, int> m;
        int cnt = 0;
        for (auto a : s) ++m[a];
        for (auto a : m) {
    
            if (a.second % 2 == 1) ++cnt;
        }
        return cnt == 0 || (s.size() % 2 == 1 && cnt == 1);
    }
};

用set也可以

class Solution {
    
public:
    bool canPermutePalindrome(string s) {
    
        unordered_set<char> st;
        for (auto a : s) {
    
            if (!st.count(a)) st.insert(a);
            else st.erase(a);
        }
        return st.empty() || st.size() == 1;
    }
};

bitset

• 建立一个 256 大小的 bitset，每个字母根据其 ASCII 码值的不同都有其对应的位置
• 然后我们遍历整个字符串，遇到一个字符，就将其对应的位置的二进制数 flip 一下，就是0变1，1变0
• 那么遍历完成后，所有出现次数为偶数的对应位置还应该为0，而出现次数为奇数的时候，对应位置就为1了
• 也就是说我们最后只要统计1的个数，就知道出现次数为奇数的字母的个数了，只要个数小于2就是回文数

class Solution {
    
public:
    bool canPermutePalindrome(string s) {
    
        bitset<256> b;
        for (auto a : s) {
    
            b.flip(a);
        }
        return b.count() < 2;
    }
};