LeetCode - 125. Valid Palindrome

[LeetCode] 125. Valid Palindrome

LeetCode 125번 문제를 풀어보았다.. Link

Problem

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome, or false otherwise.

Intuition

NeetCode Roadmap의 Two Pointers 카테고리 첫번째 문제이다.

Palindrome이란 좌우가 반전되어도 같은 문자열을 의미한다.

문자열 양쪽 끝에 포인터를 하나씩 두고 그 자리의 문자를 비교했을 때 같아야지만 Palindrome이라는 규칙을 이용하여 Left와 Right의 pointer를 두어 풀 수 있다.

다만 문제는 문자열에 띄어쓰기도 있고, 콤마도 있고, 대소문자가 섞여있고, 숫자도 있다.

따라서 문자를 제외한 나머지는 무시하고, 양 Pointer가 가리키고 있는것이 둘다 문자라면 서로 비교하여 Palindrome인지 아닌지 확인하면 된다.

(이 문제의 좋아요 싫어요 비율을 보면 싫어요가 좋아요 보다 많은걸 볼 수 있는데, 이는 사실 문제 설명대로라면 숫자도 무시해야하지만 실제로는 숫자를 무시하면 안되는 테스트 케이스가 있어, 이에 대한 유저들의 분노의 표시이다.)

Approach

1. alphanum이라는 함수를 생성. 이 함수는 숫자, 알파벳의 16진수로 변환한다음 비교하여 숫자 또는 알파벳이면 True를 반환하는 함수이다.
2. 문자열의 왼쪽부터 중간쪽으로 이동할 Left 포인터와 오른쪽에서부터 중간쪽으로 이동할 Right 포인터를 생성한다.
3. left나 right가 가리키는 것이 문자가 아니면 각각 중간으로 한칸씩 옮기고 continue한다.
4. left와 right가 가리키는 것이 둘다 문자면 둘을 비교한다.
   • 같으면 left와 right를 중간으로 한칸씩 옮긴다.
   • 다르면 Palindrome이 아니므로 False를 Return한다.
5. Left가 Right보다 작을 때 까지 반복한다.
6. True를 Return한다.

Complexity

• Time complexity:

  주어진 문자열의 길이를 n이라고 할 때, \(O(n)\)

• Space complexity: \(O(1)\)

My Code

문제의 유형을 알고풀어서 쉬웠을수도 있다.

숫자이거나 알파벳인지 아닌지 판별해야만 하는 문제들이 Easy 난이도에서는 꽤 자주 보이는 것 같은데, 필요하다면 외우는게 좋겠다.

이 문제에서 했던 방식대로 16진수로 변환한다음 그 값을 비교하는 방법도 있지만, 파이썬 내장함수로 isdigit(), isalpha()와 같은 함수들도 같이 알아놓자.

• str.isalpha() –> 해당 str이 문자열인지 알파벳인지 확인하는 문자열의 멤버함수
• str.isdigit() –> 해당 str이 숫자로만 이루어져있는지 확인하는 문자열의 멤버함수
• str.isalnum() –> 해당 str이 숫자 또는 알파벳인지 확인하는 문자열의 멤버함수

def alphanum(c):
        return (
            ord("A") <= ord(c) <= ord("Z")
            or ord("a") <= ord(c) <= ord("z")
            or ord("0") <= ord(c) <= ord("9")
        )

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s) - 1
        while left < right:
            if not alphanum(s[left]):
                left += 1
                continue
            if not alphanum(s[right]):
                right -= 1
                continue

            if s[left].lower() == s[right].lower():
                left += 1
                right -= 1
            else:
                return False
        return True