[LeetCode/Python] 125. Valid Palindrome

문제 링크:

https://leetcode.com/problems/valid-palindrome/description/?envType=study-plan-v2&envId=top-interview-150

Palindrome 에 관한 문제이다. 문제만 잘 읽는다면 문제 없이 풀 수 있다.

사실 leetcode를 풀 때 초반 장벽은 아마 영어 단어이지 않을까 싶다. 다행히 이 문제에서는 palindrome이 어떤 특징을 가진 단어인지 설명을 해주는데, 코테 문제에서는 설명을 안해주는 경우도 허다해서 난감했던 기억이 있다.

 

[내 풀이]

class Solution:
    def isPalindrome(self, s: str) -> bool:
        if len(s) == 0:
            return True
        
        start, end = 0, len(s) - 1
        while start <= end:
            if not s[start].isalnum():
                start += 1
                continue
            if not s[end].isalnum():
                end -= 1
                continue

            if s[start].lower() == s[end].lower():
                start += 1
                end -= 1
                continue
            else:
                return False
        return True

 

투 포인터 문제답게 투 포인터를 이용해서 풀었다..ㅎ...

 

시간 복잡도

isalnum(), lower()를 포함한 문자 비교: O(1)

while문 최악의 경우: O(n)

=> O(n)

 

공간 복잡도

입력 문자열 외에 추가로 사용하는 메모리는 start, end 뿐이다. 이는 입력 크기와 무관하게 일정하다.

따라서 O(1)

=> O(1)

 

[다른 풀이]

1. 정규 표현식을 이용한 풀이

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # Remove non-alphanumeric characters and convert to lowercase
        s = re.sub(r"[^A-Za-z0-9]", "", s).lower()
        
        # Check if the string is a palindrome
        return s[::-1] == s

 

아.. 오랜만에 문제 풀다보니 슬라이싱 문법을 까먹었다..

s[::-1] 는 파이썬에서 문자열을 뒤집은 슬라이싱 표현법이다. 문자열을 뒤집어서 간단하게 원래 문자열과 같은지 비교하는 코드다.

 

시간복잡도

re.sub: O(n)

[::-1]: O(n)

=> O(n)

 

공간 복잡도

re.sub() 으로 새로운 문자열 생성: O(n)

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

=> O(n)

 

 

2. 

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

이건 1번 풀이와 비슷한데, alpha + numeric만을 string에서 남겨놓는 방식이 다르다.

순회를 돌면서 일일히 letter들을 체크하고 join문으로 다시 문자열을 만들어주고 있다.

 

시간 복잡도

O(n)

 

공간 복잡도

O(n)

 

 

3. 가장 최적의 코드

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = [c.lower() for c in s if c.isalnum()]
        return all (s[i] == s[~i] for i in range(len(s)//2))

와우.. 비트 연산자 ~을 사용했다. (이건 진짜 천잰데..)

주어진 숫자의 모든 비트를 뒤집어서 논리 부정으로 풀었는데, 이 풀이를 제시한 사용자가 아래와 같이 설명했다.

~x == -x-1 이므로, 즉 ~0 == -1, ~1 == -2 .... 즉,, 뒤집은 문자열로 알아서 비교할 수 있다.

 

시간 복잡도

list comprehension: O(n)

비트 연산 비교: 최악의 경우 O(n)

=> O(n) + O(n) = O(n)

 

공간 복잡도

새로운 리스트를 생성하므로 O(n)

=> O(n)