[LeetCode] 125. Valid Palindrome

 

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

Valid Palindrome - LeetCode

팰린드롭 이란?
앞뒤가 똑같은 단어나 문장. 뒤집어도 같은 말이 된다. 우리말로는 '회문'이라고 한다.

내 풀이

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = []
 
        # 소문자로 변환
        for i in s:
            if i.isalnum():
                strs.append(i.lower())
 
        tmp = strs
 
        # 펠린드롭 판단
        while len(tmp) > 1:
            if strs.pop(0) != tmp.pop():
                return False
        return True

pop(0)이 O(n), 이것을 n번 반복하므로 O(n^2)이다.

문제에서 영문자와 숫자만을 대상으로 한다고 하였으니 isalnum()을 사용했다.
isalnum()은 문자+숫자까지 True를 리턴한다.
https://developeryuseon.tistory.com/28

[Python] isalnum(), isalpha() 함수

+) Deque를 사용하면 더 빠르게 구현 가능하다. pop(0) 보다 popleft()의 연산 속도가 더 빠르다

 

책 정보

파이썬 알고리즘 인터뷰 국내도서 저자 : 박상길 출판 : 책만 2020.07.15 상세보기