[LeetCode 해석 및 풀이] 125. Valid Palindrome

LeetCode 문제 해석 및 풀이 방법

 

문제 125. Valid Palindrome(유효한 회문)

바로가기

 

문제 설명

영문

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.

 

한글

모든 비-영숫자(alphanumeric) 문자들을 제거 후 소문자로 모두 바꾼 다음, 앞으로 읽으나 뒤로 읽으나 똑같은 문장을 회문이라 부릅니다. 영숫자 문자에는 알파벳과 숫자가 포함됩니다.

 

문자열 s가 주어질 때, s가 회문이면 true, 아니면 false를 반환하세요.

 

제한조건

• 1 <= s.length <= 2 * 105
• s consists only of printable ASCII characters.

 

입출력 예

입력	출력
s = "A man, a plan, a canal: Panama"	true
s = "race a car"	false
s = " "	true

 

 

해답 및 해설

파이썬 (Python)

neetcode 로드맵에 나온대로 2-포인터를 이용하면 쉽게 풀 수 있는 문제

class Solution:
    def isPalindrome(self, s: str) -> bool:
        def is_alphanumeric(c:str):
            code = ord(c)
            is_number = code >= 48 and code <= 57
            is_upper = code >= 65 and code <= 90
            is_lower = code >= 97 and code <= 122
            return is_number or is_upper or is_lower

        def char_lower(c:str):
            code = ord(c)
            is_lower = code >= 97 and code <= 122
            
            if is_lower:
                code += 32
                return chr(code)
            else: return c

        f = 0
        e = len(s) - 1

        while f <= e:
            while f <= len(s) -1 and (not is_alphanumeric(s[f])):
                f += 1
            while e >= 0 and (not is_alphanumeric(s[e])):
                e -= 1

            if f > len(s) -1 or e < 0: break
            
            if char_lower(s[f]) != char_lower(s[e]):
                return False

            f += 1
            e -= 1
        
        return True

 우선 맨앞과 맨 뒤에 인덱스를 하나씩 둔 후, 인덱스를 하나씩 이동해가며 글자가 같은지 체크한다. 만약 alphanumeric 문자가 아니라면 인덱스를 스킵해서 옮겨준다.

 앞쪽 인덱스와 뒷쪽 인덱스가 교차할 때까지 시행해주면 해당 문자는 회문이 맞으므로 True를, 그 전에 다른 문자가 나왔다면 False를 출력해준다.

 

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

물론 파이썬은 파이써닉하기 때문에 걍 기본 메서드들을 이용해서 이래줘도 된다.