문제

문자열이 팰린드롬(앞뒤가 같은 ex."abcba") 인지 확인하라! 대소문자 구분 X, 영어와 숫자만 취급

예시

"A man is i nama"  -> true
"race a caras" -> false

풀이

my풀이1(60ms, 19.5mb)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 전처리
        strs = []
        for char in s:
            if char.isalnum():
                strs.append(char.lower())
        # 리스트의 앞 뒤 비교
        for i in range(len(strs)):
            if strs[i] != strs[-(i + 1)]:
                return False
        return True

book풀이1(288ms, 19.2mb)

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

book풀이2(48ms, 19.1mb)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 데크 선언
        strs : Deque = collections.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

• 데트만 선언해 줘도 시간이 많이 줄어듬.
• 리스트에서 pop(0)을 해주면 O(n)인데 popleft()는 O(1)!
• 리스트 구현은 O(n2), 데크 구현은 O(n)

book풀이3(28ms, 15.4mb)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
     	# 문자, 숫자가 아닌 것 -> '' 으로 변경 s 문자열을
        s = re.sub('[^a-z0-9]', '', s)
        return s == s[::-1]

• [::-1] 리스트 뒤집기
  ex) str = "Hello", str[::-1] = "olleH"