LeetCode 266 Palindrome Permutation

LeetCode

Given a string s, return true if a permutation of the string could form a palindrome.

Example 1:

Input: s = “code”
Output: false

Example 2:

Input: s = “aab”
Output: true

Example 3:

Input: s = “carerac”
Output: true

Constraints:

1 <= s.length <= 5000 s consists of only lowercase English letters.

题目大意：

字符串的任一全排列是否存在回文字符串

解题思路：

数学题，也就是统计字符频率，奇数频率的字符最多有1个

解题步骤：

N/A

注意事项：

1. 统计字符频率，奇数频率的字符最多有1个

Python代码：

def canPermutePalindrome(self, s: str) -> bool:
	char_to_count = collections.Counter(s)
	return False if len([count for count in char_to_count.values() if count % 2 == 1]) > 1 else True

算法分析：

时间复杂度为O(n)，空间复杂度O(1)