LeetCode【0267】回文分列 II
1 中文标题给定一个字符串 s ，返回 其重新分列组合后可能构成的所有回笔墨符串，并去除重复的组合 。
可以按 恣意顺序 返回答案。假如 s 不能形成任何回文分列时，则返回一个空列表。
示例：
输入: s = "aabb"
输出: ["abba", "baab"]
输入: s = "abc"
输出: []
提示：
[*] 1 ≤ s . l e n g t h ≤ 16 1 \leq s.length \leq 16 1≤s.length≤16
[*]s 仅由小写英笔墨母组成
2 Python求解
2.1 求解思路
先统计字符频率确定中心字符(假如存在),然后利用回溯法天生字符串左半部分的所有可能分列,最后通过左半部分+中心字符+右半部分的倒序构建完整的回文串。在回溯过程中利用聚集去重避免重复分列。
2.2 涉及方法
[*]回溯算法(Backtracking)和计数排序思想(Counting Sort Concept)。
[*]回溯算法用于天生所有可能的分列
[*]计数排序思想用于统计和处置惩罚字符频率。回溯过程中通过剪枝和去重优化搜索空间。
2.3 求解示例
统计字符频率: {'a':2, 'b':2}
没有中心字符(都是偶数次)
待排列字符: ['a', 'a', 'b', 'b']
回溯生成左半部分排列:
第一步选'a': path=['a']
第二步选'a': path=['a','a']
生成回文串"aabb"
回溯,尝试其他组合
最终生成: ["aabb", "bbaa"]
2.4 Python代码
class Solution:
def generatePalindromes(self, s: str) -> List:
# 统计每个字符出现的次数
counter = Counter(s)
# 找出出现奇数次的字符
center = ''
chars = []
for char, count in counter.items():
# 如果出现奇数次,记录为中心字符
if count % 2 == 1:
# 如果已有中心字符,说明无法构成回文
if center:
return []
center = char
# 将每个字符的一半加入到待排列的字符列表中
chars.extend( * (count // 2))
# 生成所有可能的排列
def backtrack(chars, used, path):
# 如果当前路径长度等于待排列字符数,生成回文串
if len(path) == len(chars):
# 左半部分+中心字符(如果有)+右半部分的倒序
half = ''.join(path)
return ]
result = []
# 用于去重的集合
seen = set()
# 尝试每个可用的字符作为下一个字符
for i in range(len(chars)):
# 如果当前位置已使用或字符已在当前位置用过,跳过
if used or chars in seen:
continue
# 标记字符为已使用
used = True
seen.add(chars)
# 递归生成剩余字符的排列
result.extend(backtrack(chars, used, path + ]))
# 回溯,重置状态
used = False
return result
# 开始生成回文排列
used = * len(chars)
return backtrack(chars, used, [])
2.5 复杂度分析
[*]时间复杂度为O(n×n!),此中n是左半部分字符的长度(原字符串长度的一半),需要天生所有可能的分列。现实运行时间会好于这个上界,因为有去重和剪枝优化。
[*]空间复杂度为O(n),主要用于递归调用栈和存储临时结果。
3 标题总结
标题难度：中等
数据范例：字符串
数据结构：数组
应用算法：回溯算法、计数排序思想
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]