题目

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
回文串是指正反两个方向都一样的单词或词语。排列是指字母的重新排列。
回文串不一定是字典当中的单词。
image.png

思路

  1. class Solution:
  2.     def canPermutePalindrome(self, s: str) -> bool:
  3.         ch_num = dict()
  4.         for ch in s:
  5.             ch_num[ch] = ch_num.get(ch, 0) + 1
  6.         length = len(s)
  7.         tmp = [num % 2 == 0 for num in ch_num.values()]
  8.         print(tmp)
  9.         if length % 2 == 0:
  10.             # 所有字符的数量都是偶数
  11.             return all(tmp)
  12.         else:
  13.             # 有且只要一个字符的数量为奇数
  14.             return (len(ch_num) - sum(tmp)) == 1

更好的办法应该用位操作来实现。
题目理解：如果是回文，只存在1个或者0个出现次数为奇数的数（字符串转换为数字ord(ch))。
flag = 0

  • 如果字符串数量len(s)有偶数个，利用性质 flag ^ a ^a=flag的性质，遍历所有字符，最终flag = 0；
  • 如果字符数量len(s)有奇数个，那么有且只有1个字符的数量ch为1个，1左移ord(ch)必定为2的次方。判断二进制中有且只有1位为1或者是2的n次方，方法是 flag & (flag - 1) == 0
    1. class Solution:
    2.   def canPermutePalindrome(self, s: str) -> bool:
    3.       # 位运算
    4.       # a ^ a = 0
    5.       # a ^ 0 = a
    6.       flag = 0
    7.       for ch in s:
    8.           flag ^= 1 << ord(ch)
    9.       return flag & (flag - 1) == 0