# Python Backtracking solution (55ms)

• Bcktracking approach. Looks big but is pretty simple. The trick is to understand that palindrome has one odd counted char. So check that first using a hash table. Now use the keys in the hsah table for backtrcking, consuming two entries at a time and putting them in a temp array from both left and right sides. In the end, put the odd char.

``````class Solution(object):

def backtrack(self, ht, lpos, rpos, temp, result, has_odd, odd_char, even_count):
if even_count == len(ht)-1 and has_odd:
while lpos <= rpos:
temp[lpos] = odd_char
lpos += 1
result.append(''.join(temp))
return
elif not has_odd and lpos >= rpos:
result.append(''.join(temp))
return
for key, val in ht.iteritems():
if val > 1:
temp[lpos] = key
ht[key] -= 1
temp[rpos] = key
ht[key] -= 1
if ht[key] == 0:
even_count += 1
self.backtrack(ht, lpos+1, rpos-1, temp, result, has_odd, odd_char, even_count)
if ht[key] == 0:
even_count -= 1
ht[key] += 2

def generatePalindromes(self, s):
"""
:type s: str
:rtype: List[str]
"""
if not s:
return []

ht = {}

for i in range(len(s)):
ht[s[i]] = ht.get(s[i], 0) + 1

has_odd = False
odd_char = None
for c in ht:
if ht[c] & 1:
if has_odd:
return []
has_odd = True
odd_char = c
result = []
temp = ['']*len(s)
self.backtrack(ht, 0, len(s)-1, temp, result, has_odd, odd_char, 0)
return result
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.