难度: Medium
Submission
运行时间: 51 ms
内存: 23.6 MB
class Solution:
def generatePalindromes(self, s: str) -> List[str]:
letdic = {}
lets = set()
for item in s:
if item not in letdic:
letdic[item] = 1
else:
letdic[item] += 1
if item in lets:
lets.remove(item)
else:
lets.add(item)
if len(lets) >= 2:
return []
self.ans = []
def dfs(remaindict, curstr):
if len(remaindict) == 0:
self.ans.append(curstr)
return
for key in remaindict:
remainnum = remaindict[key]
dictcpy = remaindict.copy()
if remainnum == 2:
dictcpy.pop(key)
else:
dictcpy[key] -= 2
dfs(dictcpy, key+curstr+key)
if len(lets) == 1:
for item in lets:
middle = item
if letdic[middle] == 1:
letdic.pop(middle)
else:
letdic[middle] -= 1
dfs(letdic, middle)
else:
dfs(letdic, '')
return self.ans
Explain
此题解旨在找出字符串s中所有可以组成的回文排列。首先，通过统计每个字符出现的次数，并同时记录出现次数为奇数的字符集合。如果奇数字符的数量大于1，则无法形成任何回文排列，直接返回空列表。如果有一个字符出现次数为奇数，则这个字符将被放在回文的中间，其余的字符将配对使用。使用深度优先搜索（DFS）来尝试所有可能的字符排列组合，以构建回文字符串。DFS函数通过递归地选择字符对，并更新字符的使用情况，直至所有字符都被使用完。每当找到一个有效的排列时，就将其添加到答案列表中。
时间复杂度: O((n/2)!)
空间复杂度: O(n+(n/2)!)
class Solution:
def generatePalindromes(self, s: str) -> List[str]:
letdic = {} # 存储字符及其出现次数
lets = set() # 存储出现次数为奇数次的字符
for item in s:
if item not in letdic:
letdic[item] = 1
else:
letdic[item] += 1
if item in lets:
lets.remove(item)
else:
lets.add(item)
if len(lets) >= 2: # 如果奇数次字符超过1个，不能形成回文
return []
self.ans = []
def dfs(remaindict, curstr):
if len(remaindict) == 0: # 所有字符都已使用完
self.ans.append(curstr)
return
for key in remaindict:
remainnum = remaindict[key]
dictcpy = remaindict.copy() # 深拷贝当前字典
if remainnum == 2:
dictcpy.pop(key)
else:
dictcpy[key] -= 2
dfs(dictcpy, key+curstr+key) # 构建回文并递归
if len(lets) == 1: # 存在一个奇数次字符，将其放在回文中心
for item in lets:
middle = item
if letdic[middle] == 1:
letdic.pop(middle)
else:
letdic[middle] -= 1
dfs(letdic, middle) # 从包含中心字符的字符串开始DFS
else:
dfs(letdic, '') # 从空字符串开始DFS
return self.ans
Explore
在`dfs`函数中，当某个字符数量为2时直接移除该字符的处理逻辑是基于这两个字符会被放置在回文字符串的两侧。对于字符数量大于2的情况，不能直接移除，而是应该减少2个数量，因为这些字符还需要在后续的递归调用中继续构建回文结构。因此，这种处理方式并不适用于所有字符数量大于2的情况，只适用于数量正好为2的情况。
深拷贝操作（`remaindict.copy()`）会复制当前字典的所有键值对，其时间和空间复杂度与字典的大小成正比。如果字符串`s`包含大量重复字符，对应的字典`remaindict`的大小会相对较小（因为重复字符只占用一个键），这可能会减少一部分性能开销。然而，如果`remaindict`中的键的数量仍然较多，频繁的深拷贝操作确实可能导致较大的性能开销，尤其是在深度优先搜索中频繁调用时。优化方案可以考虑使用其他方法管理字符计数，以减少深拷贝的需要。
在`dfs`函数中，递归确保生成的字符串是回文结构的关键在于每次递归调用都是对称地向字符串的两端添加相同的字符。开始时，如果有一个字符的出现次数为奇数，则这个字符作为中心字符单独放置在中间，其余字符则成对出现。在递归过程中，每次选择一个字符（减去两个计数），将其添加到当前字符串的两端。这样，无论递归何时结束，当前字符串都会保持对称性，从而确保是回文结构。递归结束的条件是所有字符都被完全使用，此时生成的字符串是一个完整的回文。