[알고리즘] Leetcode #125 유효한 팰린드롬 (Python)

---

↓↓↓ 아래는 내 리트코드 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

 

---

 

문제 설명

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

 

입출력 예

Example 1:

Input	"A man, a plan, a canal: Panama"
Output	true

Example 2:

Input	"race a car"
Output	false

 

Constraints

• s consists only of printable ASCII characters.

 

CODE

s = 'A man, a plan, a canal: Panama'

# 1
# Regular Expression, slicing
import re
s = s.lower()
s = re.sub('[^a-z0-9]', '', s)
s == s[::-1]

# 2
# precleaning
strs = []
for char in s:
    if char.isalnum():
        strs.append(char.lower())

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

# 3
# Using Deque
import collections
Deque = collections.deque()
strs = Deque
for char in s:
    if char.isalnum():
        strs.append(char.lower())

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

 

팰린드롬이란 개념을 이 문제에서 처음 봤다^^.. 문자열을 뒤집었을 때 동일한 결과여야 하는데, 대/소문자 구분을 하지 않고 문자, 숫자만 비교대상으로 하기 때문에 문자열 전처리를 해줘야한다. 각 풀이에서는 정규표현식을 사용해 영어 소문자, 숫자만 걸러 내거나, isalnum() 함수를 사용해 문자, 숫자만 뽑아 리스트에 소문자로 할당해주었다.

위 세 가지 풀이 중 첫 번째 slicing을 이용한 풀이가 시간 복잡도 측면에서 가장 효율적이다. 또, 2번 풀이처럼 리스트의 pop 기능을 이용해 비교해주는 것보다 3번 풀이처럼 Deque 자료형을 이용해 popleft() 함수로 비교할 때 O(n)에서  O(1)으로 시간복잡도가 개선된다. 

* s[::-1] 은 리스트 s를 완전히 뒤집은 형태

 

---

 

I'm a Senior Student in Data Science ! 

데이터 사이언스를 공부하고 있는 4학년 학부생의 TIL 블로그입니다. 게시글이 도움 되셨다면 구독과 좋아요 :)