[LeetCode | Python] 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.

유효한 palindrome(회문) 검사하는 메서드 구현하기!

 

풀이1: Reverse String

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

newStr을 만들고

isalnum으로 아닌 건 건너뛰고, alnum인 경우 소문자로 변환하여 newStr에 저장한다.

이후 newStr와 newStr[::-1] (Reverse String)를 비교한 결과 리턴

반복문 한번 순회하는데 O(n), 마지막에 newStr[::-1]에서 Reverse String O(n)

O(n) + O(n)으로 시간 복잡도는 O(n)이다.

 

 

풀이2: Two Pointers

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l, r = 0, len(s) - 1

        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l, r = l + 1, r - 1
        return True

양 끝에서 비교하는 Two Pointers 방식으로도 풀 수 있다.

 

while l < r 안에 또 while l < r 조건이 있는 게 의아할 수도 있는데, 

s = ".,"와 같이 알파벳이나 숫자가 전혀 없는 경우를 생각해보면 된다.

l < r 검사를 가장 밖에 있는 while문에서만 하게 되면, 

s = ".,"일 때 양 끝이 모두 alnum이 아니므로 계속 l, r = l + 1, r -1로 넘어가게 된다.

결국 l은 오른쪽 끝을 넘고 r은 왼쪽 끝을 넘어 IndexError가 나게 된다.

 

isalnum 메서드

알파벳과 넘버인지 검사하는 메서드다. 아래 파이썬 공식문서의 string메서드에서 string 종류를 판별하는 메서드를 훑어보자.

https://docs.python.org/3/library/stdtypes.html#str.isalnum

Built-in Types

 

isalnum 없이 검사 함수 사용

def alphaNum(self, c):
    return (ord('A') <= ord(c) <= ord('Z') or 
            ord('a') <= ord(c) <= ord('z') or 
            ord('0') <= ord(c) <= ord('9'))

isalnum이 생각이 안난다면 위와 같이 간단하게 검사 함수를 구현해도 된다.

ord는 하나의 문자를 받아 유니코드로 반환한다. (<-> chr은 유니코드를 받아 문자열을 반환한다.)