commented Python solution


  • 0

    Sharing a Python solution. Please let me now if you have suggestions on how to improve it.

      def generatePalindromes(self, s):
        dic = {}  # NOTE: could use collections.Counter for convenience
        for l in s:
          if l not in dic: dic[l] = 1
          else:            dic[l] += 1
        odds, evens = [], []  # for odd and even numbered characters, respectively
        for l in dic:
          if dic[l] % 2 != 0:
            if odds: return [] # cannot form palindrome
            odds.append(l)
          evens += [l] * (int(dic[l] / 2))
    
        if len(evens) == 0: return odds
        res = set()
    
        def permu(i, cur, visited):  # generate permu
          newv = set(visited)
          newv.add(i)
          cur = cur + [evens[i]]
          if len(newv) == len(evens):
            half = ''.join(cur)
            res.add(half + odds[0] if odds else "" + half[::-1])
            return
          for j in range(len(evens)):
            if j not in newv:
              permu(j, cur, newv)
    
        for k in range(len(evens)):
          permu(k, [], set())
        return list(res)
    

Log in to reply
 

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