1.4 회문 순열

문제

주어진 문자열이 회문(Palindrome)의 순열인지 아닌지 확인하는 함수를 작성하라. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은 구절을 의미하며 순열이란 문자열을 재배치하는 것을 의미한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다.

 

예제 

입력 : tact coa

출력 : True 

 

접근법

어느 방향으로 읽어도 같은 문자열이 되기 위해서는 모든 문자가 각각 홀수개 이거나, 단 한개의 문자만 홀수 개여야한다.

 

방법 1 hash table을 이용하여 각 문자가 몇번 등장했는지 세고, 홀수의 갯수를 확인하기

 

방법 2 문자열을 읽어나가면서 홀수의 갯수를 세기 

def Solution(phrase):
    alpha_cnt = [0]*26
    odd_cnt = 0
    for alpha in phrase :
        alpha_cnt[ord(alpha)-ord('a')] +=1
        if alpha_cnt[ord(alpha)-ord('a')] %2 !=0 :
            odd_cnt +=1
        else :
            odd_cnt -=1
    return odd_cnt <2

 

방법 3 비트벡터를 이용하여 1로 세팅된 비트의 갯수가 1개이거나 0개인 경우를 확인한다.

def Solution(phrase):
    alpha_chk = 0
    for alpha in phrase :
        alpha_chk ^= (1<< (ord(alpha)-ord('a'))
    return alpha_chk ==0 | (alpha_chk-1) & alpha_chk ==0

여기서 신박했던 것은

이진수에서 1의 갯수가 단 하나인지를 체크할때 AND연산으로 가능하다는 것이다.

(확인할 수 -1 ) AND (확인할수) ==0 이면 1의 갯수는 1개이다

왜냐하면 만약 확인하고 싶은 수가 001000이라고 할때 -1을 하면 000111이 되고 그말은 즉 겹치는 부분이 없다는 뜻이다.

만약 확인하고 싶은 수가 101000이면 -1한 경우 100111이 되고 이경우 AND연산을하면 100000으로 0이 되지 않는다.