3. 문자열 - 유효한 펠린드롬

https://leetcode.com/problems/valid-palindrome/

Valid Palindrome - LeetCode

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

 

 3가지 해결 방법이 존재한다.

 

 첫번째는 리스트로 변환하는 방법이다.

 여기서 isalnum()는 영문자, 숫자 여부를 판별하는 함수로, 이를 이용해 해당하는 문자만 추가한다. 대소문자를 구분하지 않으므로 lower()로 모두 소문자로 변환한다.

def isPalindrome_with_list(s:str):
    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

 

 두번째는 데크 자료형을 이용한 최적화이다.

import collections

def isPalindrome_with_Deque(s:str):
    strs=collections.deque()

    for char in s:
        if char.isalnum():
            strs.append(char.lower())

    while len(strs)>1:
        if strs.popleft() != strs.pop():
            return False

 첫번째 방법 풀이 대비 거의 5배 가까이 더 속도를 높일 수 있었는데 이는 리스트의 pop(0) 가 O(n)인 데 반해, 데크의 popleft()는 O(1)이기 떄문이다. 

 

 세번째는 슬라이싱 사용이다.

import re

def isPalindrome_with_slicing(s):
    s=s.lower()
    # 정규식으로 불필요한 문자 필터링
    s=re.sub('[^a-z0-9]','',s)

    return s==s[::-1]  #슬라이싱(뒤집기)

 

풀이	방식	실행 시간
1	리스트로 변환	304밀리초
2	데크 자료형을 이용한 최적화	64밀리초
3	슬라이싱 사용	36밀리초