LeetCode 面试题 01.04. 回文排列
目录
题目描述
题意分析
给定字符串
s，判断它的字符能否重新排列成一个回文串。只要回答「能」或「不能」，不需要真的构造出那个回文串。回文串的结构约束是「位置
i与位置n-1-i的字符必须相同」，也就是说除了正中间那一格，其余字符都必须两两成对。这句话把顺序问题彻底转成了计数问题：答案只与每个字符出现了多少次有关，与它们排在哪里完全无关。输入是字符串、字符集有限（本题大小写敏感，空格也算普通字符），这是「一次扫描 + 频次表」就能定案的典型信号；题目只要布尔结果，更说明不必落到构造上。
边界：空串本身就是回文，应当返回真；串长为偶数时不允许有落单字符，串长为奇数时恰好允许一个落单字符占据正中间。注意「落单字符至多一个」这一条对奇偶长度同时成立，所以实现上不需要显式判断串长的奇偶。
解法：哈希表统计状态
核心思路
最直白的暴力是枚举
s的全排列逐个验回文，复杂度 $O(n! \cdot n)$，长度稍大就跑不动。瓶颈在于它把「顺序」当成了搜索维度，而回文性质根本不关心具体顺序。换个角度观察：一个长度为
n的回文串，从两端往中间配对可以配掉n / 2对，n为偶数时正好配完，n为奇数时正中间剩一个。反过来说，只要出现次数为奇数的字符种数不超过 1，就一定能拼出回文——把偶数次的字符对称摊到两侧，把那个奇数次的字符留一个在中心即可。这是充要条件，不是近似判断。于是要维护的状态就定下来了：
cnt[c]表示字符c在已扫描前缀中的出现次数，扫描过程的不变量是「cnt始终等于当前前缀里各字符的真实频次」。扫完全串后统计odd，即出现次数为奇数的字符种数，答案就是odd < 2。代码里的
sum += v & 1就是在数这个odd：v & 1取出频次的最低位，偶数得 0、奇数得 1，恰好是「这个字符是否落单」的指示量。
解题步骤
- 建频次表：用
Map<Character, Integer> cnt，键是字符、值是出现次数。之所以不用int[26]，是因为本题输入可能含空格、数字与大小写混排，定长小写桶会直接越界。- 一次扫描累加：
cnt.merge(s.charAt(i), 1, Integer::sum)。这里不需要任何提前判断——可行性只由最终频次决定，扫描途中的中间状态没有判定意义。- 统计奇数频次的种数：遍历
cnt.values()累加v & 1。用位与取奇偶比取模更直白地表达「只看最低位」，两者结果等价。- 判定返回：
return sum < 2。写成小于 2 而不是分别判 0 和 1，同时覆盖了偶数长度（sum必为 0）与奇数长度（sum必为 1）两种情况，所以主逻辑天然不必判断串长奇偶。以
s = "tactcoa"走一遍。扫描累加后得到cnt = {t: 2, a: 2, c: 2, o: 1}。逐项取最低位：t得 0、a得 0、c得 0、o得 1，累计sum = 1，满足1 < 2，返回真——对应的回文是tacocat，正中间正是那个落单的o。再看反例
s = "code"：cnt = {c: 1, o: 1, d: 1, e: 1}，四项最低位全是 1，sum = 4不小于 2，返回假；直观上四个互不相同的字符谁都配不成对，确实拼不出回文。
代码实现
class Solution {
public boolean canPermutePalindrome(String s) {
Map<Character, Integer> cnt = new HashMap<>();
for (int i = 0; i < s.length(); ++i) {
cnt.merge(s.charAt(i), 1, Integer::sum);
}
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为串长。一趟扫描累加频次，再遍历一次哈希表统计奇数项，哈希表规模不超过字符集大小，两段都是线性的。
空间复杂度：$O( \Sigma )$，哈希表最多存下出现过的每个不同字符，与串长无关；按 ASCII 字符集算即常数级。
关键点总结
- 看到「能否重排成某种结构」，先问这种结构的约束能不能只用计数刻画；本题的「两两成对加至多一个落单」就是把排列问题降成计数问题的钥匙。
- 「奇数频次的字符种数不超过 1」是充要条件，面试时要能顺手给出构造性说明（偶数次对称摊开、奇数次那个放中心），而不是只背结论。
- 判定条件写成
odd < 2能同时吃下奇偶两种长度，省掉一次取模分支；让边界自然落入主逻辑是面试官乐意看到的实现风格。- 字符集不确定时用哈希表，确认只有小写字母时才换定长数组；面试里主动问一句「字符范围是什么」比闷头写
int[26]稳得多。- 追问优化时的标准答案是用一个
int位掩码代替计数：每读一个字符做一次mask ^= 1 << c，最后判断mask & (mask - 1) == 0，把空间压到常数，这也是本题挂着位运算标签的原因。
易错点总结
- 用
int[26]当计数桶：s = "Aa b"→'A'与空格减去'a'都得负数，数组下标越界直接抛异常。- 统计前先转小写：
s = "Aa"→ 本题大小写敏感，两个字符各出现一次本应返回假，转小写后被合并成一个字符出现两次，误判为真。- 把空格当噪声过滤掉：
s = "ab "→ 空格是合法字符且只出现一次，过滤后sum从 3 掉到 2，判定结果与判题标准脱节。- 判定写成
sum == 1：s = "aabb"→ 全部成对，sum = 0被判成假，可abba明明是回文。- 用
cnt.size()冒充串长做奇偶判断：s = "abc"→cnt.size() = 3，按sum <= size % 2得3 <= 1才拦下；但s = "aab"时cnt.size() = 2、sum = 1，1 <= 0不成立，反把可行的用例判成假。- 累加写成
cnt.put(c, cnt.get(c) + 1)且不做缺省处理：s = "a"→ 首次get返回null，拆箱时空指针异常。merge的初始值写成 0：s = "ab"→ 所有频次恒为 0，sum恒为 0，任何输入都返回真。- 额外给空串加特判返回假：
s = ""→ 空串是合法回文，特判反而把正确答案改错；不加特判时sum = 0自然返回真。- 用位掩码优化时忘了异或而写成或：
s = "aa"→mask两次或运算后仍是1，被当成有一个落单字符；s = "aabb"则得mask = 3，mask & (mask - 1) != 0直接误判为假。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 409. 最长回文串 | 简单 | 同样按奇偶配对，但要返回最长长度，需累加偶数部分再决定是否补中心 |
| 242. 有效的字母异位词 | 简单 | 判两串频次完全相等，不涉及奇偶，可用一个数组先加后减看是否归零 |
| 383. 赎金信 | 简单 | 判的是频次包含关系而非相等，只要被减方不出现负数即可 |
| 49. 字母异位词分组 | 中等 | 把频次序列化成哈希键做分组，考点从判定变成「拿计数当 key」 |
| 387. 字符串中的第一个唯一字符 | 简单 | 需要两趟扫描，第二趟按原顺序找频次为 1 的最靠前下标，答案依赖位置 |
| 451. 根据字符出现频率排序 | 中等 | 统计之后还要按频次降序重排输出，考点落在计数排序或堆 |
| 1177. 构建回文串检测 | 中等 | 对大量子串反复问同一个奇偶问题，必须用前缀异或掩码把单次查询降到常数 |
| 1400. 构造 K 个回文字符串 | 中等 | 把「至多一个奇数」推广成「奇数种数 ≤ k ≤ 串长」的双侧判定 |
| 面试题 01.01. 判定字符是否唯一 | 简单 | 只关心频次是否超过 1，位掩码判重即可，无需完整计数 |
| 面试题 01.02. 判定是否互为字符重排 | 简单 | 先比长度再比频次，是本题「只看计数」思路的双串版本 |