125. Valid Palindrome (Two Pointers, String)

링크 - https://leetcode.com/problems/valid-palindrome/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

먼저 파이썬 내장함수를 몇가지 알아야 한다.

.isalnum(): character가 alphanumeric인지 확인하는 메서드이다. alphanumeric이면 True를 반환한다.

.lower(): character가 upper case letter이면 lower case letter로 변환해준다.

두가지 방법으로 풀 수 있다.

1) Compare with Reverse

방법은 간단하다. 주어진 s를 alnum()를 통해 필터링하고 lower()해서 새로운 String을 만든 뒤, 그것을 reversed한 String을 비교하는 것이다.

Time Complexity: O(n). 3번의 iteration을 거치게 된다. 1. non-alphanumeric글자들을 필터링 아웃하고, 남은 글자들을 lower()한다. 2. 새로 만든 String을 reversed한다. 3. 두개의 String을 비교한다.

Space Complexity: O(n). 필터링아웃하고 lower한 글자와, 그걸 reversed한 글자를 담을 공간이 필요하다.

2) Two Pointers

두개의 포인터를 사용해서 맨 처음과 끝부분에서 글자들을 비교하는 방식이다 (Traversing inwards, from both ends of the input string). 포인터를 움직일때마다 non-alphanumeric글자들은 무시하고, 비교해야할 글자들이 다르면 False를 반환하면 된다.

Time Complexity: O(n) 포인터들을 통해 String을 한번만 훑으면 되기 때문에 하나의 iteration이 필요하다. 중간에 break되서 빨리 끝날수도 있다.

Space Complexity: O(1)

Code

# 1. Compare with Reverse
class Solution:
    def isPalindrome(self, s: str) -> bool:
        filtered_chars = filter(lambda ch: ch.isalnum(), s)
        lowercase_filtered_chars = map(lambda ch: ch.lower(), filtered_chars)

		# Should use list() since output from filter() and map() is object, not String or list
        filtered_chars_list = list(lowercase_filtered_chars)
        reversed_chars_list = filtered_chars_list[::-1]
        return filtered_chars_list == reversed_chars_list

# 2. Two Pointers
class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1

        while left < right:
            while left < right and not s[left].isalnum():
                left += 1
            while left < right and not s[right].isalnum():
                right -= 1

            if s[left].lower() != s[right].lower():
                return False

            left += 1
            right -= 1

        return True