LeetCode 面试题 01.04. 回文排列
题目描述
题意分析
可以重新排列全部字符，判断是否存在正反相同的排列，不必构造结果，也不要求原字符串已经是回文。每个字符都必须保留，不能为了凑回文删掉多余字符。
解法：统计奇数频次的字符种数
核心思路
[!blue]
回文中关于中心对称的两个位置必须是同一字符，因此除中心外，每种字符都成对出现。只有奇数长度回文能在中心多放一个字符，所以出现次数为奇数的字符种类最多只能有一种。这是能够组成回文的必要条件。
这个条件也足够：把每种字符的一半放到左侧，另一半按相反顺序放到右侧；若有一种字符剩余一个，就放在中心。所有字符恰好用完，得到的排列一定是回文，因此无需尝试具体排列。
用哈希表统计每个码点的频次，再累加
v & 1。偶数频次贡献 0，奇数频次贡献 1，所以sum是奇数频次的种类数，返回sum < 2即可。总长度与奇数项数量同奇偶，这个统一条件也已经覆盖了偶数长度全成对、奇数长度只留一个中心的区别。代码按码点计数：Java 用
codePointAt读取并按Character.charCount前进，Go 用range得到rune。同一补充平面字符不会被拆成两个 UTF-16 单元或多个字节；大小写、空格仍是各自不同的字符，不额外做转换或删除。
解题步骤
- Java 逐码点读取并按 charCount 推进，Go 用 range 遍历 rune。
- 记录每个码点的总次数。
- 累加每个频次的最低位，奇数项至多一个则返回 true。
代码实现
class Solution {
public boolean canPermutePalindrome(String s) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int i = 0; i < s.length(); ) {
int c = s.codePointAt(i);
cnt.merge(c, 1, Integer::sum);
i += Character.charCount(c);
}
int sum = 0;
for (int v : cnt.values()) {
// v & 1 取频次的最低位，落单的字符贡献 1。
sum += v & 1;
}
return sum < 2;
}
}
func canPermutePalindrome(s string) bool {
cnt := map[rune]int{}
for _, c := range s {
cnt[c]++
}
sum := 0
for _, v := range cnt {
// v & 1 取频次的最低位，落单的字符贡献 1。
sum += v & 1
}
return sum < 2
}
复杂度分析
- 时间复杂度：期望 $O(n)$，
n为输入码点数，统计频次后再扫描至多n个不同码点。- 空间复杂度：$O(u)$，
u为不同码点数，保存每种字符的频次。
关键点总结
[!green]
大小写和空格按各自码点计数，不自动删空格或转换大小写；按码点处理不拆开补充平面字符。
易错点总结
[!yellow]
- 统计奇数频次的种类，不是奇数字符总个数。
- 原字符串不必已经回文，只需能重排。
- Java char 是 UTF-16 代码单元，不能把它直接当任意 Unicode 码点。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 409. 最长回文串 | 简单 | 同样利用成对字符，本题要求用完全部字符，原题允许舍弃多余奇数字符求最大长度。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！