面试题 01.04

Given a string, write a function to check if it is a permutation of a palin­ drome. A palindrome is a word or phrase that is the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.

Example1:

Input: "tactcoa" Output: true（permutations: "tacocat"、"atcocta", etc.）

Solutions

1. hash map

2. palindrome contains at most 1 characters with odd count.

class Solution {
public:
    bool canPermutePalindrome(string s) {
        vector<int> count(128);
        int odd = 0;
        for (auto c : s)
            odd += (++count[c] & 1) ? 1 : -1;

        return odd <= 1;
    }
};

or

class Solution {
public:
    bool canPermutePalindrome(string s) {
        bitset<128> m;
        for (auto c : s)
            m.flip(c);
        return m.count() <= 1;
    }
};