-
Notifications
You must be signed in to change notification settings - Fork 0
LC 0267 [M] Palindrome Permutation II
Code with Senpai edited this page Apr 20, 2022
·
1 revision
we only need to generate the first half of the string
a palindrome can only have 1 odd freq char, and if it does, it is always in the middle: [half][odd char][reversed half]
otherwise all the chars must be even: [half][reversed half]
if there is an odd, we place it in the middle and build the sides. otherwise we just build the sides
class Solution:
def generatePalindromes(self, s: str) -> List[str]:
counts = Counter(s)
odd_char = ''
# if multiple odd chars, return false
# sets the single odd char if it exists
for char in counts:
if counts[char] % 2 == 1:
if odd_char:
return []
else:
odd_char = char
counts[char] -= 1
def backtrack(cur_perm):
if len(cur_perm) == len(s) // 2:
perm = cur_perm + [odd_char] + cur_perm[::-1]
res.append(''.join(perm))
else:
for char in counts:
if counts[char] > 0:
cur_perm.append(char)
counts[char] -= 2
backtrack(cur_perm)
cur_perm.pop()
counts[char] += 2
res = []
backtrack([])
return res
footer