leetCode - valid Palindrome 유효한 팰린드롬

 

Example 1

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

 

Example 2

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

 

Example 3

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

 

 

 

Code

# 유효한 팰린드롬
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

 

데크 자료형 활용

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

 

참고 코드

class Solution:
    def isPalindrome(self, s: str) -> bool:
    	s = [i for i in s.lower() if i.isalnum()]
    	return s == s[::-1]

 

• 기본 코드의 경우 O(n^2)이지만 데크 활용시 O(1)
• 참고 코드의 경우 2줄로 깔끔하게 정리
  • 파이썬 슬라이싱 활용한 코드
  • [::-1]의 경우 뒤집는다.
    • ex) 안녕하세요 -> 요세하녕안
• isalnum() 함수의 경우 영문자, 숫자 여부를 판별하는 함수