[LeetCode] 125. Valid Palindrome [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀
문제 👉 <Valid Palindrome - LeetCode>

1. 문제 (유효한 팰린드롬)

주어진 문자열이 펠린드롬인지 확인하라.

대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다.

2. 풀이

1. 알파벳과 숫자가 아닌 경우 제외
2. 소문자 변환 (대소문자를 구분하지 않으므로)
3. 문자의 앞뒤 비교

3. 코드

• 리스트를 이용한 풀이

class Solution:
    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

• 데크를 이용한 풀이

from collections import deque

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = 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

• 슬라이싱과 정규표현식을 이용한 풀이

import re

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = s.lower()
        strs = re.sub('[^a-z0-9]', '', strs) #정규표현식

        return strs == strs[::-1] #[::-1]를 이용해 문자열 뒤집기

• 결과 :

방식	Status	Runtime	Memory	Language
리스트	[Accepted]	272 ms	19.6 MB	python3
데크	[Accepted]	48 ms	19.3 MB	python3
슬라이싱	[Accepted]	32 ms	15.7 MB	python3

• list의 pop(0)은 O(n)이지만, deque의 popleft()는 O(1)이기 때문에 각각 n번씩 반복하면, list 구현은 O(n²), deque의 구현은 O(n)이다.
• slicing은 내부적으로 C로 빠르게 구현되어 속도가 빠르다.

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋