LeetCode-Python-267. 回文配列II

1つの文字列sが与えられ、組合せを再配置することによって可能なすべての回文文字列が返され、重複する組合せが除去される.
文字列を作成できない場合は、空のリストを返します.
例1:
入力:[aabb]出力:[[abba],[baab]]例2:
入力:abc出力:[]
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/palindrome-permutation-ii著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
考え方:
まず1題の答えを調整して、解があるかどうかを判断します.
そしてアルファベットspecialが存在するかどうかを判断し、奇数回出現し、存在すればそれを探し出す.
次にspecialアルファベットを1つ削除し、出現回数を偶数回にします.
残りの仕事は、半分のsについて、前半の答えを生成し、後半の答えを前後に前半を逆転させる方法で得てつなぎ合わせることです.

class Solution(object):
    def generatePalindromes(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        if not s or not self.canPermutePalindrome(s):
            return []
        if len(set(s)) == 1:
            return [s]
        xor = s[0]
        dic = collections.Counter(s)
        
        news = "" #             s
        special = "" #         
        for key, val in dic.items():
            if val % 2:
                special = key #           
                val -= 1
            news += key * (val // 2)

        res = set()
        def permutations(word, tmp):
            if not word:
                res.add(tmp + special + tmp[::-1])
            
            for i, char in enumerate(word):
                permutations(word[:i] + word[i + 1:], tmp + char)
        permutations(news, "")
        return list(res)
                
    def canPermutePalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        flag = 0
        dic = collections.Counter(s)
        
        for key, val in dic.items():
            if val % 2:
                if not flag:
                    flag = 1
                else:
                    return False
        return True