[LeetCode] 266. Palindrome Permutation

 주어진 String의 character의 위치만 변경(permutation)해 palindrome이 가능하다면 true 불가능하면 false를 반환하는 문제다. 난이도는 Easy로 아이디어는 매우 간단하다. palindrome의 조건은 String을 앞에서 읽었을 때와 뒤에서 읽었을 때 같은 것으로, String을 구성하는 character의 종류가 모두 짝수거나 한 가지만 홀수를 가질 수 있다.

 예를 들어, "aabb"는 palindrome이 되기 위해선 "abba", 혹은 "baab"가 되면 되고 이는 'a' 또는 'b'의 위치 변경을 통해 구성이 가능하고 'a'와 'b'의 개수가 각 2개씩으로 모두 짝수다. "ccbba" 역시 1개(홀수개)인 'a'를 중앙에 위치시켜 "cbabc" 혹은 "bcacb"를 만들면 palindrome이 구성돼 모두 ture다. 간단하게 String을 구성하고 있는 각 character의 개수만 세고 홀수가 두 개를 넘어가는 순간 false를 반환한다. 

 시간 복잡도(Time Complexity)는 O(n)으로 String을 우선 한 번은 확인해야하기 때문이고, 공간 복잡도(Space Complexity)는 O(1)인데 알파벳 소문자(lowercase English letter)로 구성돼 있고 개수만 저장하면 되기 때문이다.

 

class Solution:
    def canPermutePalindrome(self, s: str) -> bool:
        dic = defaultdict(int)
        for i in range(len(s)):
            dic[s[i]] += 1
        kL = list(dic.keys())
        f = 0
        for i in range(len(kL)):
            if dic[kL[i]] % 2 == 1:
                f += 1
                if f > 1:
                    return False
        return True