[LeetCode] 267. Palindrome Permutation II

 266번 문제와 유사하다. 266번은 가능한지 불가능한지만을 true, false로 반환하면 되지만 여기서 불가능하면 깡통([])을 반환하고, true면 구성 가능한 모든 String을 반환하는 것이다. 우선 false의 경우는 266번과 같은 방식을 활용하면 되고, dfs를 통해 String을 구성해 반환하면 된다.

 

class Solution:
    def __init__(self):
        self.palL = []

    def form(self, even, pal):
        if len(even) == 0:
            self.palL.append(pal)
            return
        for i in range(len(even)):
            cur = even[i]
            copyE = even.copy()
            copyE.remove(cur)
            self.form(copyE, pal + cur)

    def generatePalindromes(self, s: str) -> List[str]:
        Solution()

        ret = []
        dic = defaultdict(int)

        for c in s:
            dic[c] += 1
        
        odd = 0
        kL = list(dic.keys())
        for k in kL:
            if dic[k] % 2 == 1:
                odd += 1
                if odd > 1:
                    return ret

        even = []
        odd = []
        for k in kL:
            if dic[k] % 2 == 0:
                while dic[k] > 0:
                    even.append(k)
                    dic[k] -= 2
            else:
                odd.append(k)
                dic[k] -= 1
                while dic[k] > 0:
                    even.append(k)
                    dic[k] -= 2
        
        self.form(even, "")

        rvs = []
        for i in range(len(self.palL)):
            rvs.append(self.palL[i][::-1])

        if len(odd) > 0:
            for i in range(len(self.palL)):
                self.palL[i] += odd[0]
        
        for i in range(len(self.palL)):
            self.palL[i] += rvs[i]

        ret = set(self.palL)
        ret = [*ret]

        return ret