Palindrome Permutation

只能有一个字母的次数是奇数次或者没有的字符串才能重构成对称字符串

class Solution(object):
    def canPermutePalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        return len([char for char, value in collections.Counter(s).items() if value % 2]) <= 1

Palindrome Permutation II

这道题有一个查重策略的问题，看起来好像各个排列是不一样的，但是实际上因为有奇数个字母的存在导致了可能有重复的方法出现（猜的？），最暴力的方法就是用一个set直接帮我们踢掉重复结果了

class Solution(object):
    def generatePalindromes(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        store = collections.Counter(s)
        if len([char for char, value in store.items() if value % 2]) > 1:
            return []

        result = set([])
        self.helper('', result, store)
        return list(result)

    def helper(self, tmp, result, store):
        if not store.keys():
            result.add(tmp[:])
            return

        for char in store.keys():
            if store[char] % 2:
                store[char] -= 1
                if not store[char]:
                    store.pop(char)
                self.helper(tmp[:len(tmp) / 2] + char + tmp[len(tmp) / 2:], result, store)
                store[char] += 1
            else:
                store[char] -= 2
                if not store[char]:
                    store.pop(char)
                self.helper(char + tmp + char, result, store)
                store[char] += 2

这里通过另外一种方法验证了上面的猜测即只有有奇数个同字符出现的字符串在排列时会产生重复问题，既然如此，我们就先把这个多出来的字符先放在中间就好了，这样就避免了额外去重

class Solution(object):
    def generatePalindromes(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        store = collections.Counter(s)
        checker = [char for char, value in store.items() if value % 2]
        if len(checker) > 1:
            return []

        tmp = ''
        if checker:
            tmp += checker[0]
            store[checker[0]] -= 1
            if not store[checker[0]]:
                store.pop(checker[0])

        result = []
        self.helper(tmp, result, store)
        return result

    def helper(self, tmp, result, store):
        if not store.keys():
            result.append(tmp[:])
            return

        for char in store.keys():
            store[char] -= 2
            if not store[char]:
                store.pop(char)
            self.helper(char + tmp + char, result, store)
            store[char] += 2