首页 > 代码库 > Permutation Palindrome

Permutation Palindrome

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

For example,
"code" -> False, "aab" -> True, "carerac" -> True.

 

Analyse: use hash map

 1 class Solution { 2 public: 3     bool canPermutePalindrome(string s) { 4         unordered_map<char, int> um; 5         for (char ch : s)  6             um[ch]++; 7          8         bool canPermute = true; 9         for (unordered_map<char, int>::iterator ite = um.begin(); ite != um.end(); ite++) {10             if (ite->second % 2) {11                 if (!canPermute) return false;12                 else canPermute = false;13             }14         }15         return true;16     }17 };

 

Analyse: use A[ch]. There are 128 characters in ASCII, we can convert a char to int automatically.

 1 class Solution { 2 public: 3     bool canPermutePalindrome(string s) { 4         vector<bool> charOccurenceBool(128, false); 5         for (char ch : s) 6             charOccurenceBool[ch] = !charOccurenceBool[ch]; 7          8         int count = 0; 9         for (int i = 0; i < charOccurenceBool.size(); i++) {10             if (charOccurenceBool[i]) count++;11         }12         return count < 2;13     }14 };

 

Permutation Palindrome