[파이썬 알고리즘 인터뷰] 팰린드롬 판별 | 리스트, deque, 슬라이싱

박상길, 『파이썬 알고리즘 인터뷰』를 정리한 내용입니다.

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

Valid Palindrome - LeetCode

---

문제 요약

• 주어진 문자열이 팰린드롬인지 확인하라
• 팰린드롬 : 앞뒤가 똑같은 단어나 문장. 뒤집어도 같은 말이 되는 단어 또는 문장
• 영문자와 숫자만 판별한다. 대소문자는 구분하지 않는다.

---

전처리

영문자와 숫자만 판별하기 때문에 공백과 기호는 비교하면 안된다

대소문자를 구분하지 않기 때문에 모든 영문자는 소문자로 변환하는 것이 좋다. 

 

다음과 같이 리스트나 deque에 소문자와 숫자만 넣는다.

strs = [] 		#팰린드롬 판별에 사용할 리스트
for c in s:  	#s : input string
    if c.isalnum():
        strs.append(c.lower())

 

정규식을 사용해 문자를 필터링한다

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

---

방법 1 : list의 pop 메서드를 사용해 팰린드롬 판별

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

---

방법 2 : deque의 popleft, pop 메서드를 사용해 팰린드롬 판별

리스트의 pop(0)는 O(n)인데 deque의 popleft는 O(1)이기 때문에 deque를 사용하면 성능을 높일 수 있다

from collections import deque

def isPalindrome(s):
    strs = deque()
    for c in s:
        if c.isalnum():
            strs.append(c.lower())

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

---

방법 3 : list의 슬라이싱을 사용해 팰린드롬 판별

input string을 소문자와 숫자로만 이루어진 문자열로 변환 후 슬라이싱 기능을 이용해 뒤집은 문자열과 비교한다

슬라이싱은 내부적으로 C로 구현되어있기때문에 속도가 훨씬 빠르다.

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

    return s == s[::-1]