Article / 文章
LeetCode 第267题：回文排列 II
给定一个字符串 s，返回其通过重新排列组合后所有可能的回文字符串，并去除重复的组合。 如不能形成任何回文排列时，则返回一个空列表。
📖 文章摘要
本文详细解析LeetCode第267题“回文排列 II”，这是一道回溯算法的中等难度问题。文章提供了从基础回文判断到高效回溯生成的完整解法思路，包含多种语言实现，配有详细的回溯过程图解和去重技巧分析。适合想要深入理解回溯算法和字符串处理的算法学习者。
核心知识点： 回溯算法、字符串处理、全排列生成、去重技巧
难度等级： 中等
推荐人群： 回溯算法学习者、字符串处理爱好者
题目描述
给定一个字符串 s，返回其通过重新排列组合后所有可能的回文字符串，并去除重复的组合。
如不能形成任何回文排列时，则返回一个空列表。
示例
示例 1：
输入: "aabb"
输出: ["abba", "baab"]示例 2：
输入: "abc"
输出: []提示
- 字符串长度不会超过16。
- 字符串仅包含小写英文字母。
解题思路
这道题是 LeetCode第266题：回文排列 的扩展，不仅需要判断字符串能否重排为回文串，还需要列出所有可能的回文排列。
核心分析
回文串的特性：
- 偶数长度：所有字符都必须出现偶数次
- 奇数长度：最多只能有一个字符出现奇数次
解题策略：
- 先判断能否形成回文排列
- 利用回文串的对称性，只需生成前半部分
- 使用回溯算法生成所有可能的前半部分排列
- 对每个前半部分构造完整的回文串
算法步骤
步骤1：预处理和可行性检查
- 统计每个字符出现的次数
- 确定是否可以形成回文排列（最多一个字符出现奇数次）
- 提取中间字符（如果有）和前半部分字符
步骤2：回溯生成排列
- 对前半部分字符进行全排列
- 使用回溯算法，注意去重处理
- 对每个排列构建完整的回文串
复杂度分析：
- 时间复杂度：O((n/2)!)，主要由全排列的生成决定
- 空间复杂度：O(n + (n/2)!)，包括存储结果和递归栈空间
图解思路
算法步骤分析表
| 步骤 | 输入示例 | 操作 | 结果 | 说明 |
|---|---|---|---|---|
| 预处理 | “aabb” | 统计字符频率 | {a:2, b:2} | 所有字符出现偶数次 |
| 可行性 | {a:2, b:2} | 检查奇数字符数 | 0 ≤ 1 | 可以形成回文排列 |
| 提取字符 | {a:2, b:2} | 构建前半部分 | [‘a’, ‘b’] | 每个字符取一半 |
| 回溯排列 | [‘a’, ‘b’] | 生成全排列 | [“ab”, “ba”] | 去重的全排列 |
| 构建回文 | [“ab”, “ba”] | 前半+后半 | [“abba”, “baab”] | 镜像构建完整回文 |
回溯过程分析表
以输入“aabb”为例的回溯树：
| 层级 | 当前路径 | 可选字符 | 操作 | 结果 |
|---|---|---|---|---|
| 0 | [] | [‘a’, ‘b’] | 开始回溯 | 选择第一个字符 |
| 1 | [‘a’] | [‘b’] | 选择’a’ | 继续深入 |
| 2 | [‘a’, ‘b’] | [] | 选择’b’ | 生成“abba” |
| 1 | [‘b’] | [‘a’] | 回溯选择’b’ | 继续深入 |
| 2 | [‘b’, ‘a’] | [] | 选择’a’ | 生成“baab” |
代码实现
C# 实现
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
public class Solution {
public IList<string> GeneratePalindromes(string s) {
var result = new List<string>();
if (string.IsNullOrEmpty(s)) return result;
// 统计字符出现次数
int[] count = new int[128];
foreach (char c in s) {
count[c]++;
}
// 检查是否可以形成回文
int oddCount = 0;
char oddChar = '\0';
for (int i = 0; i < 128; i++) {
if (count[i] % 2 != 0) {
oddCount++;
oddChar = (char)i;
}
}
if (oddCount > 1) return result;
// 构建字符列表（前半部分）
var chars = new List<char>();
for (int i = 0; i < 128; i++) {
for (int j = 0; j < count[i] / 2; j++) {
chars.Add((char)i);
}
}
// 使用回溯生成所有可能的排列
bool[] used = new bool[chars.Count];
var sb = new StringBuilder();
Backtrack(chars, used, sb, oddChar, result);
return result;
}
private void Backtrack(List<char> chars, bool[] used,
StringBuilder sb, char oddChar, List<string> result) {
if (sb.Length == chars.Count) {
// 构建完整的回文串
string half = sb.ToString();
string palindrome = half + (oddChar != '\0' ? oddChar.ToString() : "") +
new string(half.Reverse().ToArray());
result.Add(palindrome);
return;
}
for (int i = 0; i < chars.Count; i++) {
// 跳过重复字符（去重关键）
if (used[i] || (i > 0 && chars[i] == chars[i-1] && !used[i-1])) {
continue;
}
used[i] = true;
sb.Append(chars[i]);
Backtrack(chars, used, sb, oddChar, result);
sb.Length--;
used[i] = false;
}
}
}Python 实现
class Solution:
def generatePalindromes(self, s: str) -> List[str]:
if not s:
return []
# 统计字符出现次数
count = {}
for c in s:
count[c] = count.get(c, 0) + 1
# 检查是否可以形成回文
odd_chars = [c for c, v in count.items() if v % 2 != 0]
if len(odd_chars) > 1:
return []
# 构建字符列表（前半部分）
chars = []
for c, v in count.items():
chars.extend([c] * (v // 2))
# 排序以便去重
chars.sort()
# 使用回溯生成所有可能的排列
result = []
used = [False] * len(chars)
def backtrack(curr):
if len(curr) == len(chars):
# 构建完整的回文串
half = ''.join(curr)
palindrome = half + (odd_chars[0] if odd_chars else '') + half[::-1]
result.append(palindrome)
return
for i in range(len(chars)):
# 跳过重复字符（去重关键）
if used[i] or (i > 0 and chars[i] == chars[i-1] and not used[i-1]):
continue
used[i] = True
curr.append(chars[i])
backtrack(curr)
curr.pop()
used[i] = False
backtrack([])
return resultC++ 实现
class Solution {
public:
vector<string> generatePalindromes(string s) {
vector<string> result;
if (s.empty()) return result;
// 统计字符出现次数
vector<int> count(128, 0);
for (char c : s) {
count[c]++;
}
// 检查是否可以形成回文
int oddCount = 0;
char oddChar = 0;
for (int i = 0; i < 128; i++) {
if (count[i] % 2 != 0) {
oddCount++;
oddChar = (char)i;
}
}
if (oddCount > 1) return result;
// 构建字符列表（前半部分）
vector<char> chars;
for (int i = 0; i < 128; i++) {
for (int j = 0; j < count[i] / 2; j++) {
chars.push_back((char)i);
}
}
// 使用回溯生成所有可能的排列
vector<bool> used(chars.size(), false);
string curr;
backtrack(chars, used, curr, oddChar, result);
return result;
}
private:
void backtrack(vector<char>& chars, vector<bool>& used, string& curr,
char oddChar, vector<string>& result) {
if (curr.length() == chars.size()) {
// 构建完整的回文串
string half = curr;
string palindrome = half + (oddChar ? string(1, oddChar) : "") +
string(half.rbegin(), half.rend());
result.push_back(palindrome);
return;
}
for (int i = 0; i < chars.size(); i++) {
// 跳过重复字符（去重关键）
if (used[i] || (i > 0 && chars[i] == chars[i-1] && !used[i-1])) {
continue;
}
used[i] = true;
curr.push_back(chars[i]);
backtrack(chars, used, curr, oddChar, result);
curr.pop_back();
used[i] = false;
}
}
};执行结果
C# 实现
- 执行用时：88 ms
- 内存消耗：39.8 MB
Python 实现
- 执行用时：56 ms
- 内存消耗：16.4 MB
C++ 实现
- 执行用时：4 ms
- 内存消耗：8.2 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C++ | 4 ms | 8.2 MB | 性能最佳，内存占用最小 |
| Python | 56 ms | 16.4 MB | 代码简洁，内存占用适中 |
| C# | 88 ms | 39.8 MB | 代码结构清晰，但性能相对较差 |
代码亮点
- 🎯 巧妙地将问题分为两部分：可行性判断 + 回溯生成，降低问题复杂度
- 💡 利用回文串的对称性，只需生成前半部分，大大减少计算量
- 🔍 使用经典的去重技巧：排序+跳过重复，确保结果无重复
- 🎨 回溯模板清晰，选择-递归-撤销的三步骤结构完整
常见错误分析
- 🚫 忘记检查字符串是否能形成回文排列，直接开始生成排列
- 🚫 没有正确处理出现奇数次的字符，导致回文构建错误
- 🚫 全排列过程中没有去重，导致结果中有重复的回文串
- 🚫 构建回文串时，前半部分和后半部分的镜像关系处理错误
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 回溯算法 | O((n/2)!) | O(n + (n/2)!) | 利用对称性优化，结果无重复 | 实现复杂度较高 |
| 暴力全排列 | O(n!) | O(n + n!) | 思路直观 | 时间复杂度过高，需要额外去重 |
| 字符组合 | O((n/2)!) | O(n + (n/2)!) | 直接生成，避免中间步骤 | 代码复杂，难以理解 |
相关题目
- LeetCode 266. 回文排列 - 简单
- LeetCode 46. 全排列 - 中等
- LeetCode 47. 全排列 II - 中等
- LeetCode 5. 最长回文子串 - 中等
📖 系列导航
🔥 算法专题合集 - 查看完整合集
📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第267题。
💬 互动交流
感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。
如果这篇文章对你有帮助，请：
- 👍 点个赞，让更多人看到这篇文章
- 📁 收藏文章，方便后续查阅复习
- 🔔 关注作者，获取更多高质量算法题解
- 💭 评论区留言，分享你的解题思路或提出疑问
你的支持是我持续分享的动力！
💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！