[Top Interview Questions] 125. Valid Palindrome

정답)

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

        while left < right:
            if s[right].isalnum() and s[left].isalnum():
                if s[right].lower() != s[left].lower():
                    return False
                left += 1
                right -= 1
                    
            elif not s[left].isalnum():
                left += 1
                
            elif not s[right].isalnum():
                right -= 1
            
        return True

문제)

문제 출처

 

팰린드롬 (회문)은 거꾸로 읽어도 똑같은 문장을 뜻합니다.

이 문제에서는 대문자들을 전부 소문자 취급하고 알파벳과 숫자를 제외한 문자들은 취급하지 않습니다.

 

스트링 s가 주어졌을 때, s가 팰린드롬이면 True를, 아니라면 False를 리턴하시오.

 

예시 1)

s = "A man, a plan, a canal: Panama"

output = True

"amanaplanacanalpanama"는 거꾸로 읽어도 똑같음.

 

예시 2)

s = "race a car"

output = False

 

예시 3)

s = " "

output = True

스페이스는 알파벳과 숫자가 아닙니다. 고로 취급하지 않는다면 s는 ""겠죠.

빈 스트링은 거꾸로 읽어도 빈 스트링이기 때문에 팰린드롬입니다.

풀이)

이번 문제도 굉장히 직관적일 것입니다. 아마 못 푸셨다면 제가 사용하는 메서드를 보시면 푸실 수 있으실 겁니다.

기본원리)

두 개의 포인터 left와 right을 이용합니다.

left는 0번째부터, right은 -1번째부터 중간까지 선형 합니다.

 

선형 하는 도중 알파벳 혹은 숫자를 발견하면 비교합니다.

만약 원소들이 같다면 다음 원소로 넘어가고

다르다면 바로 False를 리턴해 함수를 종료합니다.

 

선형하는 도중 알파벳 혹은 숫자가 아닌 원소를 발견할 수도 있습니다.

무시하고 다음 원소로 넘어갑니다.

 

그렇게 모든 원소들을 확인했다면 s가 팰린드롬이라는 뜻이므로 True를 리턴합니다.

 

class Solution:
    def isPalindrome(self, s: str) -> bool:
        2개의 포인터들 left, right

        올바른 범위 안에서
            s[right]와 s[left] 둘 다 숫자거나 알파벳일 때
                2개의 원소가 같지 않다면 바로 False를 리턴
                    
            s[left]가 조건에 맞지 않을 때 left 포인터를 업데이트       
                
            s[right]이 조건에 맞지 않을 때 right 포인터를 업데이트
            
        선형이 완료됬다면 True를 리턴

2개의 포인터들)

팰린드롬은 앞에서 읽으나 뒤에서 읽으나 같아야지 팰린드롬입니다.

 

그렇다면 저희도 앞에서 읽고 뒤에서 읽으면서 문자들을 비교하면 팰린드롬인지 확인할 수 있겠죠?

그래서 left를 0에 right을 -1번째에 지정해 줍시다. 

 

def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s)-1

올바른 범위)

제 짧은 릿코드 경험상 포인터 2개 사용하는 경우에는 대부분 범위를 left와 right을 이용해 구분합니다.

 

그렇다면 이번엔 left < right일까요? left <= right 일까요?

 

left <= right일 경우에는 검색하는 배열 혹은 문자열의 가장 가운데를 비교해야 되는 경우입니다.

 

하지만 팰린드롬과 같은 경우에는 중간을 굳이 비교할 필요가 없죠?

중간이 어떤 문자건 중요하지 않고 그 중간을 기점으로 대칭이면 되기 때문이죠.

 

def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s)-1

        while left < right:

isalnum(), lower())

이번 문제에 아주 유용한 2개의 메서드가 스트링에 존재합니다.

바로 .isalnum() 과 .lower() 입니다.

 

.isalnum()은 문자/문자열이 알파벳 혹은 숫자인지 여부를 알려주는 메서드입니다.

'a'.isalnum()을 할 경우 True를 리턴합니다.

'?'.isalnum()을 할 경우 False를 리턴합니다.

 

.lower()는 문자/문자열의 알파벳을 전부 소문자화 시킵니다. 그리고 기호나 숫자들은 무시해 주기 때문에 이번 문제에 굉장히 편리하죠.

조건에 적합한 문자들을 발견)

먼저 s[right]와 s[left]가 둘 다 알파벳/숫자 인지 isalnum() 메서드를 이용해 확인해 줍니다.

만약 둘 다 알파벳/숫자라면 lower() 메서드를 이용해 소문자화 시켜주고 2개의 문자들이 다르다면 False를 리턴하게 해 줍니다.

 

소문자화한 원소들이 같다면 별다른 조치 없이 넘어가줍니다. 

왜냐하면 저희는 문자열의 끝에서 중간까지 계속 선형 해줘야 하기 때문입니다.

 

그리고 비교가 끝났다면 다음 원소를 확인하기 위해 left를 1칸 오른쪽 right을 1칸 왼쪽으로 옮겨 줍니다.

 

def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s)-1

        while left < right:
            if s[right].isalnum() and s[left].isalnum():
                if s[right].lower() != s[left].lower():
                    return False
                left += 1
                right -= 1

만약 두 문자 모두 조건에 적합하지 않다면)

두 문자 모두 적합하지 않다는 것은 둘 중에 하나 혹은 둘 다 조건에 적합하지 않다는 뜻이죠.

 

어느 경우인지 모르기 때문에 elif를 이용해 두 문자 모두 확인해 주겠습니다.

만약 알파벳/숫자가 아니라면 각 포인터들을 업데이트해줍니다.

 

이런 식으로 문자열을 전부 확인했고 따로 False가 리턴되지 않았다면 이 문자열은 팰린드롬이라는 뜻이기 때문에 True를 리턴합니다.

 

def isPalindrome(self, s: str) -> bool:
        left = 0
        right = len(s)-1

        while left < right:
            if s[right].isalnum() and s[left].isalnum():
                if s[right].lower() != s[left].lower():
                    return False
                left += 1
                right -= 1

            elif not s[left].isalnum():
                left += 1
            elif not s[right].isalnum():
                right -= 1
            
        return True

디버깅)

s = "race e car"

 

left = 0

right = 9

 

(while 0 < 9)

left = 1

right = 8

 

(while  1 < 8)

left = 2

right = 7

 

(while 2 < 7)

left = 3

right = 6

 

(while 3 < 6)

right = 5

 

(while 3 < 5)

left = 4

right = 4

 

return True

 

 

이번 문제도 나름 직관적인 문제였던 거 같은데요. 아마 isalnum()과 lower() 메서드를 아셨다면 쉽게 풀었을 것이라고 생각합니다.

 

오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)