程序员面试金典 - 面试题 01.04. 回文排列

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。

回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。

回文串不一定是字典当中的单词。

示例 1：

输入："tactcoa"
输出：true（排列有"tacocat"、"atcocta"，等等）

题目思考

1. 什么字符串是回文串的排列？
2. 能否做到常数空间复杂度？

解决方案

思路

• 分析题目，输入不需要是回文串，只需要其某种排列满足回文串即可，所以我们可以从回文串的性质入手
• 回文串有两种形式：一种是中间单独一个字符，两边对称；还有一种是最中间两个字符也对称。
• 也就是说，回文串中最多只有一个字符的出现次数为 1，其他都必须为偶数
• 所以我们可以使用一个计数字典来统计是否满足上述要求即可
• 以上就是核心的思路，接下来我们考虑如何优化空间。这里我们无需知道精确的次数，而是只需要知道奇偶性，所以我们可以利用异或操作，这样就只需要一个变量而不需要字典了。具体做法如下：
  • 使用一个 mask + 字符的 ASCII 码来统计奇偶
  • 每次遍历一个字符就把对应位取异或
  • 这样最后如果 mask 上最多只有一个 1，则说明最多只有一个奇数次数的字符，满足题意
  • 这里判断是否最多有一个 1 可以复用统计 1 的个数的方法，即mask & (mask-1)：如果它是 0，则说明要么 mask 本身是 0；要么 mask 是 2 的幂，一定只有一个 1

复杂度

• 时间复杂度 O(N): 需要遍历字符串一遍
• 空间复杂度: 使用计数字典 - O(N)；使用位运算 - O(1)

代码

方案 1 - 计数字典

from collections import defaultdict


class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        # 方法1: 计数字典, 最多只能有一个字符计数为奇数
        d = defaultdict(int)
        for c in s:
            d[c] += 1
        # 判断次数为奇数的字符个数最多为1
        return sum(x & 1 for x in d.values()) <= 1

方案 2 - 异或位运算

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        # 方法2: 位运算, 异或1<<ord, 最多只有一位是1才可以!
        mask = 0
        for c in s:
            mask ^= 1 << ord(c)
        return mask & (mask - 1) == 0

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊