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

Valid Palindrome - LeetCode

 

풀이 # 1

def isPalindrome(self, s:str) -> bool:
    strs=[]
    for char in s:
        if char.isalnum():
            strs.append(char.lower())

    # 팰린드롬 여부 판별
    while len(strs) > 1:
        if strs.pop(0)!=strs.pop():
            return False
    
    return True

• str.isalnum() : 알파벳, 숫자인지 파악

풀이 # 2

def isPalindrome(self, s:str) -> bool:
    strs : Deque = collections.deque()
    for char in s:
        if char.isalnum():
            strs.append(char.lower())

    # 팰린드롬 여부 판별
    while len(strs) > 1:
        if strs.popleft()!=strs.pop():
            return False
    
    return True

• collections.deque() : 큐 자료구조 지원

deque()를 사용함으로서 # 1에 비해 5배 빠른 성능 구현( pop(0) : O(n), popleft() : O(1) )

 

풀이 # 3

def isPalindrome(self, s:str) -> bool:
    s = s.lower()
    s = re.sub('[^a-z0-9]','',s)

    return s == s[::-1]

• re.sub( 정규표현식, 대상문자열, 문자열) : 정규표현식 문자열 치환

정규표현식과 슬라이싱을 통해 #2에 비해 2배 빠른 성능을 보임.