LeetCode 267. 回文排列 II
目录
题目描述
题意分析
给一个字符串
s，要求返回它的所有不重复的回文排列。所谓回文排列，是指用s里全部字符重新排列后得到的、正读反读一样的串。如果一个都构造不出来，返回空列表。「用全部字符重排」说明字符的多重集合是固定的，我们能改变的只有顺序；「回文」则给顺序加上了一个强约束：位置
i的字符必须等于位置n-1-i的字符。把这两点合起来看，字符必须成对出现在对称位置上，只有正中间那一个位置（当且仅当n是奇数时存在）可以孤零零地站着。这直接推出可行性判据：统计每个字符的出现次数，出现奇数次的字符最多只能有一个。有两个及以上就必然有字符配不成对，也塞不进唯一的中心位，无解。
更重要的是，这个观察把问题的自由度砍掉了一半。回文串的右半段完全由左半段镜像决定，中心字符也被唯一确定（就是那个出现奇数次的字符，若不存在则中心为空）。所以真正需要枚举的只是左半段，长度是 $\lfloor n/2 \rfloor$，而它的字符多重集合就是「每个字符取出现次数的一半」。
「不重复」这三个字是第二个考点。
s里的相同字符彼此不可区分，若把它们当成不同元素做全排列，"aabb"会产出 4 个结果而其中只有 2 个互异。所以必须在枚举时做去重，而不是先全生成再用集合过滤——后者虽然答案对，但白白算了阶乘倍的重复分支。数据规模上
s长度在 16 以内，半串最长 8，$8! = 40320$，枚举半串的全排列完全可行；但若不砍掉一半自由度而去枚举整串的 $16!$ 排列，则彻底不可行。这个规模本身就是「只枚举半串」的信号。边界：空串的回文排列是空串本身（一个结果）；单字符串只有它自己；全部字符出现偶数次时中心为空，半串长度恰为 $n/2$；无解时返回空列表而不是含空串的列表。
解法：回溯 + 哈希表
核心思路
回文右半段由左半段唯一决定，因此无需枚举整个字符串。统计频次后，出现奇数次的字符最多只能有一个；它固定放在中心，每个字符的一半频次组成待排列的左半串。
左半串是多重集合。按字符顺序构造它，使相同字符相邻；回溯时使用访问数组，并在同一层跳过“前一个相同字符尚未使用”的候选，强制相同字符按下标顺序被选择，从源头消除重复排列。
状态
backtrack(index)表示path[0..index-1]已填好，used精确标记半串中已被选取的下标。填满后，唯一构造left + center + reverse(left)。正确性说明：频次奇数超过一个时不存在回文。可行时，每个回文与其左半串排列一一对应；回溯枚举所有不同的半串排列，同层剪枝只删除交换相同字符下标产生的重复分支，不删除任何不同字符序列。因此输出包含全部且仅包含不重复的回文排列。
解题步骤
- 统计字符频次，并找出唯一可能的中心字符；奇数频次超过一个则返回空列表。
- 按字符顺序把每种字符的
count / 2个副本加入半串。- 用
path、used回溯生成半串排列。- 同层遇到相同字符且前一个副本尚未使用时跳过。
- 半串填满后镜像构造完整回文并加入结果。
"aabb"的半串为"ab"，得到"abba"、"baab"；"aaaa"的半串含两个相同 a，剪枝后只生成一次"aaaa"；"abc"有三个奇数频次，直接无解。空串会生成唯一结果""。
代码实现
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<String> generatePalindromes(String s) {
int[] count = new int[128];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i)]++;
}
String center = "";
StringBuilder halfBuilder = new StringBuilder();
for (int c = 0; c < count.length; c++) {
if ((count[c] & 1) != 0) {
if (!center.isEmpty()) {
return new ArrayList<>();
}
center = String.valueOf((char) c);
}
for (int pairs = count[c] / 2; pairs > 0; pairs--) {
halfBuilder.append((char) c);
}
}
char[] half = halfBuilder.toString().toCharArray();
List<String> result = new ArrayList<>();
backtrack(
half, new boolean[half.length], new char[half.length],
0, center, result);
return result;
}
private void backtrack(
char[] half,
boolean[] used,
char[] path,
int index,
String center,
List<String> result) {
if (index == half.length) {
String left = new String(path);
result.add(left + center + new StringBuilder(left).reverse());
return;
}
for (int i = 0; i < half.length; i++) {
if (used[i]) {
continue;
}
if (i > 0 && half[i] == half[i - 1] && !used[i - 1]) {
continue;
}
used[i] = true;
path[index] = half[i];
backtrack(half, used, path, index + 1, center, result);
used[i] = false;
}
}
}
func generatePalindromes(s string) []string {
count := [128]int{}
for i := 0; i < len(s); i++ {
count[s[i]]++
}
center := ""
half := make([]byte, 0, len(s)/2)
for c, frequency := range count {
if frequency%2 != 0 {
if center != "" {
return []string{}
}
center = string(byte(c))
}
for pairs := frequency / 2; pairs > 0; pairs-- {
half = append(half, byte(c))
}
}
result := make([]string, 0)
path := make([]byte, len(half))
used := make([]bool, len(half))
var backtrack func(int)
backtrack = func(index int) {
if index == len(half) {
right := make([]byte, len(path))
for i := range path {
right[len(path)-1-i] = path[i]
}
result = append(result, string(path)+center+string(right))
return
}
for i := range half {
if used[i] {
continue
}
if i > 0 && half[i] == half[i-1] && !used[i-1] {
continue
}
used[i] = true
path[index] = half[i]
backtrack(index + 1)
used[i] = false
}
}
backtrack(0)
return result
}
复杂度分析
- 时间复杂度：$O(h! \cdot n)$，其中 $h=\lfloor n/2 \rfloor$。最坏枚举 h 个互异字符的全部排列，每个答案构造长度为 n 的字符串。
- 空间复杂度：$O(n)$（不计输出）。半串、路径、访问数组和递归深度均为线性级。
关键点总结
- 回文结构把搜索自由度减半：只排列左半串，右半串镜像生成。
- 奇数频次至多一个是回溯前的可行性判据，奇数字符固定在中心。
- 有序半串配合同层去重条件，保证相同字符只按一种下标顺序使用。
- 结果与回溯状态都应属于本次调用，避免同一
Solution重复调用时串数据。
易错点总结
- 完全不做同层去重：
"aaaa"会输出两个相同的"aaaa"。- 去重条件写成
used[i-1]：会剪掉连续使用相同字符的合法路径，"aaaa"反而无解。- 奇数频次达到一个就判无解：
"aab"可以生成"aba"，只有超过一个才无解。- 把中心字符加入半串排列：会改变字符串长度和字符使用次数。
- 忘记撤销
used[i]：第一条路径结束后状态污染兄弟分支，导致漏解。- 把结果保存为未重置成员字段：同一
Solution的第二次调用会混入第一次结果；应使用调用内局部列表。- 无解返回
null或[""]："abc"的正确结果是空列表；空串输入才返回包含空串的列表。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 面试题 01.04. 回文排列 | 简单 | 只需判定可行性不必构造，一次频次统计即可，是本题预处理阶段的独立版 |
| 47. 全排列 II | 中等 | 本题回溯部分的原型，考察排序后同层去重的标准模板与 !visited[i-1] 语义 |
| 46. 全排列 | 中等 | 元素互异无需去重，用来对照理解去重条件到底多做了什么 |
| 31. 下一个排列 | 中等 | 提供本题的迭代替代解，靠字典序递推枚举半串，$O(1)$ 额外空间且天然去重 |
| 409. 最长回文串 | 简单 | 同样按奇偶频次配对，但求的是最大长度而非构造方案，中心只能用一次 |
| 1400. 构造 K 个回文字符串 | 中等 | 把「奇数次字符至多一个」推广到「至多 k 个」，考察判据的泛化 |
| 131. 分割回文串 | 中等 | 回溯对象从排列变成切割点，回文判定要在搜索中反复进行而非由构造保证 |
| 784. 字母大小写全排列 | 中等 | 每层是二选一而非全枚举，用来对比「选择集合大小」如何决定复杂度量级 |