# LeetCode: 267. 回文排列 II¶

## 1、题目描述¶

示例 1：



## 2、解题思路¶

• 排列生成法（超时）
• 超时的主要原因是因为没考虑到很多重复字符
from itertools import permutations
from collections import Counter

class Solution:
def generatePalindromes(self, s: str) -> [str]:
c = Counter(s)

center = 0
temp = []
for key, value in c.items():
if value & 1:
if center:
return []
value -= 1
center = key

temp.extend([key] * (value // 2))

res = set()
for i in permutations(temp):
if center:
res.add("".join(i) + center + "".join(reversed(i)))

else:
return list(res)


## - 使用dfs回溯法生成全排列，并且去重¶

class Solution:
def generatePalindromes(self, s: str) -> [str]:
from collections import Counter
c = Counter(s)
center = 0
temp = []
for key, value in c.items():
if value & 1:
if center:
return []
value -= 1
center = key

temp.extend([key] * (value // 2))

res = set()

if not temp and center:
return list(res)

def dfs(string, k):

if k == len(string) - 1:
res.add("".join(string) + (center if center else "") + "".join(reversed(string)))
return
else:

for i in range(k, len(string)):
# 去重复
if i == k or string[i] != string[k]:
string[i], string[k] = string[k], string[i]
dfs(string, k + 1)
string[i], string[k] = string[k], string[i]

dfs(temp, 0)
return list(res)