3 月 13 日 每日一题
题目：266. Palindrome Permutation
Given a string, determine if a permutation of the string could form a palindrome.
1
2
3
4
5
6
7
8
9
10
11
12
13
| Example 1:
Input: "code"
Output: false
Example 2:
Input: "aab"
Output: true
Example 3:
Input: "carerac"
Output: true
|
思路
本题考虑两种情况，length 为奇数和 length 为偶数，若为偶数所有字母都出现偶数次，若为奇数，只有一个字母出现奇数次。利用 hashmap 记录字母出现频率。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
bool canPermutePalindrome(string s) {
unordered_map<char, int>counts;
size_t size = s.length();
int num = 0;
for(auto c:s){
counts[c]++;
}
for(auto count:counts){
if(count.second % 2 == 1){
num++;
}
}
return num == 0 || (num == 1 && size % 2 == 1);
}
};
|