My Readable Python Solution With Comments


  • 1
    Y
    class Solution(object):
        def generatePalindromes(self, s):
            if len(s) == 0:
                return []
                
            if len(s) == 1:
                return [s]
    
            # put the characters that have been seen twice in chars list
            chars = []
            char_set = set([])
            for c in s:
                if c in char_set:
                    chars.append(c)
                    char_set.remove(c)
                else:
                    char_set.add(c)
                
            # none of the permutations can be palindromic 
            if len(char_set) > 1:
                return []
                
            mid = '' if not char_set else char_set.pop()
            
            # put the permutations of chars into list permutations
            permutations= []
            self.getPermutations(permutations, [], [False]*len(chars), chars)
            
            return [x + mid + x[::-1] for x in permutations] 
            
        def getPermutations(self, result, item, used, chars):
            if len(item) == len(chars):
                result.append(''.join(item))
                return
            
            for i in range(len(chars)):
                if used[i]:
                    continue
        
                # avoid duplicates
                if i > 0 and chars[i-1] == chars[i] and not used[i-1]:
                    continue
                
                used[i] = True 
                item.append(chars[i])
                self.getPermutations(result, item, used, chars)
                item.pop()
                used[i] = False

Log in to reply
 

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