[LeetCode] Valid Palindrome

문제 이동
난이도 : ⭐️

펠린드롬이란?
'소주 만병만 주소'처럼 뒤집어도 똑같은 문자열

첫 번째 제출 코드

import re
class Solution:
    def isPalindrome(self, s: str) -> bool:
        cleaned_s = re.sub('[^a-z0-9]', '', s.lower())
        
        if cleaned_s[::-1] == cleaned_s:
            return True

Runtime : 35 ms
Memory : 15.6 MB

두 번째 제출 코드

import re
class Solution:
    def isPalindrome(self, s: str) -> bool:
        cleaned_s = re.sub('[^a-z0-9]', '', s.lower())
        
        return cleaned_s[::-1] == cleaned_s

Runtime : 45 ms
Memory : 15.7 MB

점수 산출 방법 때문인지 위의 두 코드가 크게 다른 점이 없는데 Runtime 속도에 10ms 차이가 난다.

+)

본인이 제출한 슬라이싱 방법 외에도 리스트, 데크를 통해 펠린드롬 문제를 풀 수 있다.
속도는 슬라이싱 < 데크 < 리스트 으로 슬라이싱이 가장 빠르다.

배운 점

• 같은 코드에서 자료형만 바꾸더라도 성능이 매우 크게 향상할 수 있다. (리스트 -> 데크)

  	deque의 popleft() :  O(1)
  	list의 pop(0) : O(n)

• 슬라이싱이 이 중 가장 빠른 이유는 내부적으로 C로 구현되어있기 때문이다. => 문자열 문제는 우선 슬라이싱으로!

• isalnum() 함수를 통해 영문자, 숫자 여부를 판별할 수 있다. (char.isalnum())

• re.sub를 통해 여러 문자를 한 번에 변경할 수 있다.
  re.sub('[^a-z0-9]', '', str) : 소문자 영문자와 숫자 외 문자는 모두 제거