程序员面试金典 - 面试题 01.04. 回文排列
题目难度: 简单
原题链接[1]
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述给定一个字符串 ， 编写一个函数判定其是否为某个回文串的排列之一 。
回文串是指正反两个方向都一样的单词或短语 。 排列是指字母的重新排列 。
回文串不一定是字典当中的单词 。
示例 1：输入："tactcoa" 输出：true（排列有"tacocat"、"atcocta" ， 等等）
题目思考
- 什么字符串是回文串的排列？
- 能否做到常数空间复杂度？
- 分析题目 ， 输入不需要是回文串 ， 只需要其某种排列满足回文串即可 ， 所以我们可以从回文串的性质入手
- 回文串有两种形式：一种是中间单独一个字符 ， 两边对称；还有一种是最中间两个字符也对称 。
- 也就是说 ， 回文串中最多只有一个字符的出现次数为 1 ， 其他都必须为偶数
- 所以我们可以使用一个计数字典来统计是否满足上述要求即可
- 以上就是核心的思路 ， 接下来我们考虑如何优化空间 。 这里我们无需知道精确的次数 ， 而是只需要知道奇偶性 ， 所以我们可以利用异或操作 ， 这样就只需要一个变量而不需要字典了 。 具体做法如下： 使用一个 mask + 字符的 ASCII 码来统计奇偶每次遍历一个字符就把对应位取异或这样最后如果 mask 上最多只有一个 1 ， 则说明最多只有一个奇数次数的字符 ， 满足题意这里判断是否最多有一个 1 可以复用统计 1 的个数的方法 ， 即mask--tt-darkmode-color: #959595;">复杂度
- 时间复杂度 O(N): 需要遍历字符串一遍
- 空间复杂度: 使用计数字典 - O(N)；使用位运算 - O(1)
from collections import defaultdictclass Solution:def canPermutePalindrome(self, s: str) -> bool:# 方法1: 计数字典, 最多只能有一个字符计数为奇数d = defaultdict(int)for c in s:d[c] += 1# 判断次数为奇数的字符个数最多为1return sum(x & 1 for x in d.values()) <= 1方案 2 - 异或位运算class Solution:def canPermutePalindrome(self, s: str) -> bool:# 方法2: 位运算, 异或1<
【程序员面试金典 - 面试题 01.04. 回文排列】原题链接:
推荐阅读
- 程序员为教师妻子开发应用：将iPhone变成文档摄像头
- 悔哭！一程序员误把7500个比特币当垃圾扔掉，估算约2.4亿美元
- 2.4亿美元打水漂！程序员小哥把7500个比特币当垃圾扔掉 硬盘找不回
- 程序员开发抢茅台脚本：2天就刷榜Github
- 为什么我喜欢C语言，却非常讨厌C++？一位国外程序员的回答
- 程序员怎么保护头发？雷军回应
- 北美程序员Tinder翻车实录
- 导航|攻坚“卫星导航信号弱”难题，高德程序员联手武大学子夺得国际室内定位大赛冠军
- 长沙|视频｜聚焦“数字英雄”长沙银行冠名全国首档程序员电视真人秀
- 孙玲|从流水线女工逆袭成高薪程序员 一度爆红的她现在咋样了？
