leetcode: 266. All Palindromic Permutations

题目来源

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

题目描述

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

题目解析

思路

回文序列：

• If the length of the string is an odd length,Only one letter appears an odd number of times,其余均为偶数
• If the length of the string is parity length,The number of occurrences of each letter must be an even number

实现

同一个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 Different code values ​​have their corresponding positions
• Then we iterate over the entire string,遇到一个字符,Just put the binary number of its corresponding position flip 一下,就是0变1,1变0
• Then after the traversal is complete,All corresponding positions with an even number of occurrences should also be 0,And when the number of occurrences is odd,对应位置就为1了
• That is to say, we only need statistics in the end1的个数,You know the number of letters with odd occurrences,as long as the number is less than2就是回文数

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