01 유효한 팰린드롬 (Valid Palindrome)

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

 

예제:

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

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

 

💡 palindrome(팰린드롬)? 앞 뒤가 똑같은 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장

 

 

솔루션:

 

• 리스트로 변환

# 리스트 활용 시간 복잡도 : O(n²)
def isPalindrome(self, s:str) -> bool:
  strs = []
  for char in s:
    if char.isalnum():  # isalnum()을 통해 영문자 숫자 판별
      strs.append(char.lower())
      
  while len(strs) > 1: # 팰린드롬 판별 여부
    if strs.pop(0) != strs.pop(): # 맨앞 글자랑 맨 뒷글자랑 비교해서 다르면 False 같으면 True
      return False
  return True

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

# 데크 활용 시간 복잡도 : O(n)
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.pop(0) != strs.pop():
      return False
  
  return True

 

문제 출처: https://leetcode.com/problems/valid-palindrome/