Leetcode 125 - Valid Palindrome

문제 링크 : leetcode 125

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

원래 나의 풀이

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        s = list(s)
    
        lst = []

        for i in s:
            if i.isalpha() == True or i.isnumeric() == True:
                lst.append(i)

        if lst == lst[::-1]:
            return True
        else:
            return False    

s.lower()함수를 통해서 대문자로 되어있는 문자를 소문자로 변경하고 각 문자에 대해서 알파벳인지, 숫자인지 확인하여 lst리스트에 넣었다. 그렇게 하여서 뒤집은 문자와 그냥 문자가 같은지 다른지를 확인하였다.

몰랐던 사실

• s변수에 따로 저장하지 않아도 s.lower()만 하면 s변수에 저장되는 줄 알았다. s.lower()이런 함수를 쓸 때 변경사항이 있다면 반드시 저장 해두어야 한다.

시간복잡도

메모리 사용량

정답으로 인정은 되었지만 메모리 사용량, 시간복잡도가 50%이상이므로 개선할 필요가 있다고 생각되었다.

다른 풀이

1. 리스트를 활용한 풀이

class Solution:
    def isPalindrome(self, s: str) -> bool:
        lst = []
        
        for i in s:
            if i.isalnum():
                lst.append(i.lower())
        
        # 펠린드롬 여부 확인
        while len(lst) > 1:
            if lst.pop(0) != lst.pop():
                return False
            
        return True   

몰랐던 사실

숫자와 알파벳을 동시에 확인할 수 있는 alnum()이라는 함수가 있다는 것을 알았다.

시간복잡도와 메모리 사용량

300ms에 19.6메모리 정도가 사용되어서 리스트를 활용한 풀이는 상당히 비효율적이라는 것을 알 수 있다.

2. 데크 자료형을 이용한 최적화

리스트만으로 충분히 문제를 해결할 수 있지만, 데크를 명시적으로 선언하면 속돌르 좀 더 높일 수 있다.

from collections import deque

class Solution:
    def isPalindrome(self, s: str) -> bool:
        q = deque()
        
        for i in s:
            if i.isalnum():
                q.append(i.lower())
        
        # 펠린드롬 여부 확인
        while len(q) > 1:
            if q.popleft() != q.pop():
                return False
            
        return True
    

시간복잡도와 메모리 사용량

큐 자료형을 통해 시간복잡도를 엄청나게 줄일 수 있었지만 메모리 사용량은 줄이지 못했다.

슬라이싱, 정규표현식 사용

알파벳과 숫자를 제외한 문자를 제거할 때 포문을 이용하여 일일이 확인하지 않고 정규표현식을 사용하여 불필요한 문자를 필터링하는 방식을 사용하였다.

그리고 펠린드롬 일치여부를 슬라이싱을 통해 옳고 그른지 판단하였다.

import re
# 정규 표현식을 활용한 효율적인 풀이
def isPalindrome(s):
    s = s.lower()
    
    # a-z, 0-9까지 단어를 제외한 단어들을 모두 ''로 대체하겠다.
    s = re.sub('[^a-z0-9]','',s)
    
    return s == s[::-1] 

정규표현식)
import re를 통해서 패키지를 로딩해주는 것 잊지말자.

시간복잡도