LeetCode 267. 回文排列 II
题目描述
题意分析
使用字符串中的全部字符，生成所有不重复的回文排列。每个字符的使用次数必须与原字符串一致，无法组成回文时返回空列表。
回文左右两半互为镜像，只要确定左半部分以及可能存在的中心字符，整个结果就已经确定，因此只需要枚举半串的不同排列。
解法：半串排列 + 回溯去重
核心思路
[!blue]
回文中除中心位外，字符都要成对出现，所以最多只能有一种字符出现奇数次。超过一种就无法配对；否则，每种字符拿出
count[c] / 2个放入半串，唯一剩下的奇数次字符放在中心。这既是必要条件，也足以构造回文，因为任意半串排列都可以镜像补全。按字符编码顺序构造
half，让相同字符相邻。回溯中的index表示当前要填的半串位置，path保存已经填好的前缀，used[i]表示半串中第i个字符副本是否已经被本条路径使用。只检查
used还不能去重：相同字符的不同副本交换使用顺序，会生成同一个字符串。因此如果当前字符与前一个字符相同，且前一个副本还未使用，就跳过当前副本，优先使用更靠前的那个。这个判断去掉的是同一位置上的重复选择。若前一个相同副本已经使用，说明它占据了当前路径中的更早位置，此时仍然允许选择下一个副本。这样固定相同副本的先后顺序，既能用完所有重复字符，又不会因为交换副本身份而重复输出。
当
path填满半串长度时，拼接“左半串 + 中心字符 + 左半串逆序”得到完整回文。不同半串排列会得到不同回文，所有合法回文也都有这样的半串，因此无需在结果中再去重。递归返回后恢复used[i]，让这个副本能参与其他分支。
解题步骤
- 统计字符频次，找出奇数次字符；发现第二种奇数次字符时立即返回空列表。
- 按字符顺序，把每种字符一半的数量加入
half，并保存可能存在的中心字符。- 从半串下标 0 开始回溯，每层枚举未使用的副本，并跳过前一个相同副本尚未使用的选择。
- 选中后标记
used[i]、写入path[index]，递归填下一位；返回后撤销访问标记。- 半串填满就镜像构造一个结果，所有分支结束后返回完整列表。半串为空但存在中心字符时，也会直接生成这个单字符回文。
代码实现
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
}
复杂度分析
设原串长度为
n，半串长度为h = n / 2。
- 时间复杂度：$O(h!\cdot n)$ 的上界。半串至多有
h!个排列，每个完整回文的构造需要 $O(n)$；重复字符会减少实际搜索分支和结果数量。- 空间复杂度：不计输出为 $O(n)$，用于半串、路径、访问标记和递归栈；每个返回的回文另占 $O(n)$ 空间。
关键点总结
[!green]
- 奇数频次最多一个，其余字符对半分配，中心位无需再排列。
- 只枚举左半串，镜像部分唯一确定，避免在整个字符串上做无效排列。
- 同层去重固定相同副本的选择顺序，不会禁止多个相同字符出现在同一路径中。
易错点总结
[!yellow]
- 完全不做同层去重：交换相同字符的不同下标会产生相同回文。
- 构造半串时没有让相同字符相邻：只比较当前字符和前一个字符，就无法完整识别同层的重复选择。
- 把中心字符额外放进半串：会改变字符使用次数，导致长度或频次不符。
- 只要存在奇数频次就判无解：允许一个字符占据中心，只有超过一个奇数频次才不可能。
- 递归返回后不恢复
used：后续分支将无法再选择这个字符副本。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 面试题 01.04. 回文排列 | 简单 | 先用奇数频次数量判断是否可行，本题再排列半边并镜像生成完整回文。 |
| 47. 全排列 II | 中等 | 半边字符可能重复，复用排序后的同层去重排列，避免输出重复回文。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！