博文中会简要介绍Leetcode P0266题目分析及解题思路。
“Palindrome Permutation”是一道比较简单的题目。题目要求检查给定的字符串能否形成一个回文串。
Given a string s, return true if a permutation of the string could form a palindrome.
这道题的思路比较简单直接。我们只需要判断，若字符串长度为奇数，那么有且仅有一个字符，出现的次数为奇数，其余字符出现次数为偶数；若字符串长度为偶数，那么所有的字符出现次数都是偶数。
以下是Java的题解代码实现。
class Solution {
public boolean canPermutePalindrome(String s) {
int L = s.length(), limit = (L%2 == 0)? 0: 1;
Map<Character, Integer> ch2CountMap = new HashMap<>();
for (int i=0; i<L; ++i) {
char c = s.charAt(i);
ch2CountMap.put(c, ch2CountMap.getOrDefault(c, 0)+1);
}
for (int count: ch2CountMap.values()) {
limit -= (count%2 == 0)? 0: 1;
}
return (limit == 0);
}
}
以下是C++的题解代码实现。
class Solution {
public:
bool canPermutePalindrome(string s) {
int L = s.length(), limit = (L%2 == 0)? 0: 1;
unordered_map<char, int> ch2count;
for (char c: s) {
ch2count[c] += 1;
}
for (auto entry: ch2count) {
limit -= (entry.second%2 == 0)? 0: 1;
}
return (limit == 0);
}
};