[Python] Leet Code 125 : Valid Palindrome 풀이 및 분석

본 내용은 <파이썬 알고리즘 인터뷰>를 참고했습니다.

Leet Code 125 : Valid Palindrome

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

포인트

• .isalnum() : alphabet, number인지 판단
• .pop(0) : 맨 앞 원소 pop, 그러나 O(n)으로 속도가 느림

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

포인트

• deque 선언
• list에서 .pop(0) 대신 deque의 .popleft()를 하면 속도 up!

def isPalindrome(self, s: str) -> bool:

    s = s.lower()
    s = re.sub('[^a-z0-9]', '', s)

    return s == s[::-1]

포인트

• 정규표현식 + 문자열 slicing이 가장 빠름
• re.sub() : 문자 대체
• []안에서 ^는 반대를 뜻한다
• 즉, 알파벳 소문자와 숫자에 해당하지 않는 모든 것들을 ''로 대체