[파이썬알고리즘 인터뷰] 유효한 팰린드롬 구하기

출처: 파이썬 알고리즘 인터뷰 6장 

주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다

1. "A man, a plan, a canal: Panama" -> true
2. "race a car" -> false

test = "A man, a plan, a canal: Panama"
test2 = "race a car" 

 

# 풀이1. 리스트로 변환 
def isPalindrome(sentence):
    # 전처리 
    strs = []
    for char in sentence:
        if char.isalnum():
            strs.append(char.lower())
    # 팰린드롬 여부 판별 
    while len(strs) > 1:
        if strs.pop(0) != strs.pop(): # 첫번째꺼를 꺼내서 마지막 꺼를 꺼내서 갖지 않으면 
            return False
    
    return True

# 풀이2. 데크자료형을 이용한 최적화 
import collections

def isPalindrome(s) -> bool:
    # 자료형 데크로 선언 
    Deque = collections.deque()
    
    for char in s:
        if char.isalnum():
            Deque.append(char.lower())
    
    while len(Deque) > 1:
        if Deque.popleft() != Deque.pop():
            return False
        
    return True

# 풀이3 슬라이싱 사용 
import re 

def isPalindrome(s) -> bool:
    s = s.lower()
    # 정규식으로 불필요한 무자 필터링
    s = re.sub('[^a-z0-9]','',s)
    
    return s == s[::-1] # 스라이싱