Skip to content

267 Palindrome Permutation II

267. Palindrome Permutation II

题目: https://leetcode.com/problems/palindrome-permutation-ii/

难度 : Medium

思路:

首先这个题目有个简单版本,那就是判断是否可以permutate 为 palindrome. 问题的关键是最多只能一个odd character.

写的这么不elegant,我也是服气!

AC代码:

class Solution(object):
    def generatePalindromes(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        def permuteUnique(firstS):
            if len(firstS) == 0 : return []
            if len(firstS) == 1 : return [firstS]
            res = []
            for i in range(len(firstS)):
                if i > 0 and firstS[i] == firstS[i-1]: continue
                for j in permuteUnique(firstS[:i] + firstS[i+1:]):
                    res.append([firstS[i]] + j)
            return res

        lookup = {}
        for char in s:
            lookup[char] = lookup.get(char, 0) + 1

        res, firstS, oddChar = 0, [], ''
        for char, cnt in lookup.items():
            if cnt % 2 == 0:
                for i in range(cnt/2):
                    firstS.append(char)
                continue
            else:
                for i in range(cnt / 2):
                    firstS.append(char)
                oddChar = char
                res += 1
        if res >= 2:
            return []
        else:
            res = permuteUnique(firstS)
            if len(res) == 0 and oddChar:
                return [oddChar]
            return map(lambda x: ''.join(x) + oddChar + ''.join(x[::-1]),res)



回到顶部