难度: Easy
Submission
运行时间: 22 ms
内存: 16.0 MB
class Solution:
def canPermutePalindrome(self, s: str) -> bool:
n = len(s)
hashmap = set()
for ch in s:
if ch not in hashmap:
hashmap.add(ch)
else:
hashmap.remove(ch)
if len(hashmap) == 0: return True
elif len(hashmap) > 1: return False
elif len(hashmap) == 1:
if n % 2 == 1: return True
else: return False
Explain
这个题解的思路是统计字符串中每个字符出现的次数，利用一个哈希集合 (set) 来记录出现奇数次的字符。最后根据出现奇数次字符的个数，判断能否构成回文排列。具体来说： 1. 遍历字符串中的每个字符 2. 如果当前字符不在哈希集合中，就把它加入集合 3. 如果当前字符已经在哈希集合中，就把它从集合中移除 4. 遍历结束后，如果哈希集合为空，说明所有字符都出现偶数次，可以构成回文排列 5. 如果哈希集合大小超过1，说明有两个以上的字符出现奇数次，无法构成回文排列 6. 如果哈希集合大小为1，且字符串长度为奇数，则可以构成回文排列（出现奇数次的字符可以放在中间）；如果字符串长度为偶数，则无法构成回文排列
时间复杂度: O(n)
空间复杂度: O(k), k <= n
class Solution:
def canPermutePalindrome(self, s: str) -> bool:
n = len(s)
hashmap = set()
for ch in s:
if ch not in hashmap:
hashmap.add(ch) # 如果当前字符不在哈希集合中，就把它加入集合
else:
hashmap.remove(ch) # 如果当前字符已经在哈希集合中，就把它从集合中移除
if len(hashmap) == 0: return True # 如果哈希集合为空，说明所有字符都出现偶数次，可以构成回文排列
elif len(hashmap) > 1: return False # 如果哈希集合大小超过1，说明有两个以上的字符出现奇数次，无法构成回文排列
elif len(hashmap) == 1:
if n % 2 == 1: return True # 如果哈希集合大小为1，且字符串长度为奇数，可以构成回文排列
else: return False # 如果哈希集合大小为1，但字符串长度为偶数，无法构成回文排列
Explore
在哈希集合中，每次遇到一个字符时，如果该字符不在集合中，则添加它；如果已存在，则移除它。这种操作意味着如果字符出现奇数次，最终会留在集合中；如果出现偶数次，则会被完全移除。因此，集合中剩下的字符都是出现奇数次的，而被移除的字符都是出现偶数次的。
不可以。如果字符串的长度是偶数，那么所有字符都应该成对出现（偶数次）以构成回文。哈希集合中有一个字符说明它出现了奇数次，这与字符串长度为偶数的场景矛盾，因此无法通过重排成为回文排列。
哈希集合大小为1时意味着只有一个字符出现了奇数次，其他所有字符都出现了偶数次。在字符串长度为奇数的情况下，这个出现奇数次的字符可以置于中心，两边对称排列出现偶数次的字符，从而构成回文排列。如果字符串长度为偶数，则所有字符都必须出现偶数次才能对称排列，因此大小为1的集合在这种情况下不适用。
使用哈希集合的方法优势在于操作简单且空间复杂度低，只需要存储最多26个字母的字符状态，不需要额外的空间来统计每个字符的具体次数。劣势是它只能用于计算奇偶性，不能提供其他更详细的字符计数信息。相比之下，直接统计每个字符的出现次数虽然能提供更详细的信息，但在某些情况下会增加空间和时间的开销。