4 lines Python solution


  • 6

    Use collections.Counter and itertools.permutations

    class Solution(object):
        def generatePalindromes(self, s):
            d = collections.Counter(s)
            m = tuple(k for k, v in d.iteritems() if v % 2)
            p = ''.join(k*(v/2) for k, v in d.iteritems())
            return [''.join(i + m + i[::-1]) for i in set(itertools.permutations(p))] if len(m) < 2 else []

  • 0
    C

    Nice solution, you are quite familiar with Python!


  • 0

    Not really...


  • 0

    Nice one. Though we should really have a test case like s = 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa' ... (you'd get TLE, even though there is just a single possibility).


  • 0

    Of course it's not optimal.


  • 0
    Y

    Agree with stefan, and not sure if these advanced methods are ok for job interviews...


  • 0

    @StefanPochmann Thanks, just added your test case.


  • 0

    I had a similar solution, but I got timeout for s = 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa'

        def generatePalindromes(self, s):
            """
            :type s: str
            :rtype: List[str]
            """
            word_count = collections.Counter(s)
            odd_char, odd_elemnts, compressed, result = '', 0, [], []
            for w in word_count:
                if word_count[w] % 2 == 1:
                    odd_elemnts += 1
                    odd_char = w
                for _ in range(word_count[w] / 2):
                    compressed.append(w)
            if odd_elemnts > 1:
                return []
    
            words_set = set()
            for l in itertools.permutations(compressed):
                word = ''.join(l)
                if word not in words_set:
                    words_set.add(word)
                    palindrome = word+odd_char+word[::-1]
                    result.append(palindrome)
            return result
    

  • 0

    @xcv58 It is so concise.


Log in to reply
 

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