266. Palindrome Permutation

本文主要是介绍266. Palindrome Permutation，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem

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

For example,
“code” -> False, “aab” -> True, “carerac” -> True.

Hint:

Consider the palindromes of odd vs even length. What difference do you notice?
Count the frequency of each character.
If each character occurs even number of times, then it must be a palindrome. How about character which occurs odd number of times?

Solution

Brute-force会超时

class Solution {
public:bool isPalindrome(const string& s){int i = 0;int j = s.length() - 1;while(i<=j){if(s[i] != s[j])return false;++i;--j;}return true;}bool canPermutePalindrome(string s) {sort(s.begin(),s.end());do{if(isPalindrome(s))return true;}while(next_permutation(s.begin(),s.end()));return false;}
};

根据hint，使用map

看了讨论区

class Solution {
public:bool canPermutePalindrome(string s) {map<char,int> charCount;for(int i = 0;i<s.length();++i){charCount[s[i]]++;}int count = 0;for(map<char,int>::iterator it = charCount.begin();it != charCount.end();++it){if(it->second % 2)++count;if(count > 1)return false;}return true;}
};

这篇关于266. Palindrome Permutation的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---