palindrome-permutation

Palindrome Permutation – LeetCode 266

Problem

Description

Given a string, determine if a permutation of the string could form a palindrome.

Answer

Original

Code

class Solution {
public:
    bool canPermutePalindrome(string s) {
		unsigned cmap = 0;
		for(unsigned i = 0; i != s.size(); ++i)
			cmap ^= 0x1 << (s[i] - '0');
		return !((cmap - 1) & cmap);
    }
};

思路

统计每个字符的出现次数，偶数个字符时要求出现次数全部为偶数个，奇数个字符时要求只能有一个字符出现次数为奇数。通过位操作进行性能优化。时间复杂度$O(n)$，空间复杂度$O(n)$。

Better

思路

还没看到更好的思路。