Python Backtracking solution (55ms)


  • 0
    A

    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
    

Log in to reply
 

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