[LeetCode] 125.Valid Palindrome (Python)

Problem

 

Solution

string

이전 Palindrome number 와 유사한 문제.

대/소문자를 모두 대문자 or 소문자로 변환하고

. , ! ? 와 같은 punctuation과 white space 을 제거 후 palindrome 인지 체크한다.

이전에 파이썬 문법 중 string 을 거꾸로 뒤집는 방법을 알아서 string[::-1] 을 사용했다.

 

다른 사람의 풀이를 보니 isalnum() 메소드로 알파벳 or 숫자만 필터링하고 join 해서 아주 간단하게 풀었다.

def isPalindrome(self, s: str) -> bool:
        s = ''.join([char for char in s if char.isalnum()]).lower()
        return s == s[::-1]

 

Code

class Solution:
    def isPalindrome(self, s: str) -> bool:
        answer = False
        s = s.lower()
        translator = str.maketrans('', '', string.punctuation)
        cleaned_string = s.translate(translator)
        cleaned_string = cleaned_string.replace(' ', '')

        if len(cleaned_string) <= 0:
            return True

        return cleaned_string == cleaned_string[::-1]

 

Complexity

Time Complexity

문자열 s 의 길이만큼 s.lower() , s.translate(translator), replace, cleaned_string[::-1] 작업 을 수행하므로

결과적으로 O(n) 의 시간 복잡도를 가진다.

 

Space Complexity

s.slower() -> 새로운 문자열 생성 O(n)

s.translate(translator) -> 새로운 문자열 생성 O(n)

replace()  -> 새로운 문자열 생성 O(n)

cleaned_string[::-1] -> 새로운 문자열 생성 O(n)

전체 공간 복잡도는 O(n)