难度: Easy
给定一个字符串,编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。
示例1:
输入:"tactcoa" 输出:true(排列有"tacocat"、"atcocta",等等)
难度: Easy
给定一个字符串,编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。
示例1:
输入:"tactcoa" 输出:true(排列有"tacocat"、"atcocta",等等)
运行时间: 23 ms
内存: 15.9 MB
class Solution: def canPermutePalindrome(self, s: str) -> bool: dict = {} for i in s: if i in dict.keys(): dict[i] += 1 else: dict[i] = 1 odd = 0 for i in dict.values(): if i % 2 == 1: odd += 1 if odd > 1: return False return True
此题解通过使用哈希表记录字符串中每个字符出现的次数。然后遍历哈希表,统计有多少个字符出现奇数次。根据回文串的性质,一个字符串如果能够重排成回文串,那么最多只能有一个字符出现奇数次(位于回文中心)。如果超过一个字符出现奇数次,则不能形成回文串。因此,算法的核心是通过检查出现次数为奇数的字符的数量,来判断是否可能重排为回文串。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution: def canPermutePalindrome(self, s: str) -> bool: dict = {} # 遍历字符串,统计每个字符的出现次数 for i in s: if i in dict.keys(): dict[i] += 1 else: dict[i] = 1 odd = 0 # 遍历字典,统计出现奇数次的字符数量 for i in dict.values(): if i % 2 == 1: odd += 1 # 如果超过一个字符出现奇数次,则不能形成回文串 if odd > 1: return False return True
哈希表(或在Python中称为字典)提供了非常高效的键值对存储机制,允许快速插入、访问和更新操作,其平均时间复杂度为O(1)。这使得它非常适合用于统计字符频率,因为我们可以直接通过字符作为键快速定位到其频率计数。而其他数据结构如数组或列表则需要手动管理索引或进行额外的计算来达到同样的效果,通常效率较低。
是的,该判断方法已经考虑了所有字符都出现偶数次的情况。在遍历字典统计奇数次出现的字符数量的过程中,如果所有字符都是偶数次,那么`odd`变量将保持为0。因此,算法最终将返回True,正确地表示字符串可以重排成回文串。
在Python中,字典的`keys()`方法返回一个视图对象,这个对象反映了字典键的实时视图,其访问效率很高。但在检查或更新字典条目时,使用`keys()`方法实际上是不必要的,因为可以直接使用`in`关键字检查键是否存在于字典中(例如`if i in dict`),这样更直接且效率更高。更新条目时,可以直接通过赋值操作来完成(例如`dict[i] = 1`),无需预先检查键是否存在。