267 Palindrome Permutation II
Given a string
s, return all the palindromic permutations (without duplicates) of it. Return an empty list if no palindromic permutation could be form.For example:
Given
s = "aabb", return["abba", "baab"].Given
s = "abc", return[].The Idea: This algorithm take ideas from two different concepts and combines them. First: how can we accurately define what is palindromic? A palindrome has some
[baseStr] + [midElement] + [reverse(baseStr)]. Note that both baseStrand midElement can be the empty string, so this definition follows true for both even and odd length strings. We can identify these components by counting the occurrences of s into a hash table. There can only be ever a single instance (at most) of an odd frequency (from which 1 it's elements has to be within the center of the string), otherwise s can not be a palindrome. There can be 0 or more instances of an even frequency.Second: once these components are identified, we can then generate all the permutations of
baseStr, and append to a solution vector for [baseStr] + [midElement] + [reverse(baseStr)]Complexity: O(n!) time and O(|unique(s)|) extra space
from collections import Counter
class Solution:
def permuteUnique(self, iterable):
sol = ['']
for it in iterable:
next_sol = []
for prev in sol:
for i in range(0, len(prev) + 1):
next_sol.append(prev[:i] + it + prev[i:])
if i < len(prev) and prev[i] == it:
break
sol = next_sol
return sol
def generatePalindromes(self, s):
"""
:type s: str
:rtype: List[str]
"""
c = Counter(s)
mid, base = '', ''
for char, freq in c.items():
if freq % 2 == 1 and mid:
return []
elif freq % 2 == 1:
mid = char
if freq > 1:
base += char * (freq // 2)
else:
base += char * (freq // 2)
all_perms = self.permuteUnique(base)
palindrome = []
for base_perm in all_perms:
palindrome.append(base_perm+mid+base_perm[::-1])
return palindrome
Last modified 4yr ago