[Leetcode] 125. Valid Palindrome_해설, 풀이, 설명

---

안녕하세요, HELLO

 

오늘은 Leetcode 알고리즘 문제 '125. Valid Palindrome'에 대해서 살펴보고자 합니다.

 

알고리즘 문제, 코드, 해설 그리고 Leetcode에서 제공해준 solution 순서대로 정리하였습니다.

---

STEP 1. 'Valid Palindrome' 알고리즘 문제

 

STEP 2. 'Valid Palindrome' 코드(code)

 

STEP 3. 'Valid Palindrome' 해설

 

STEP 4. 'Valid Palindrome' solution

 

반응형

 

STEP 1. '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.

모든 대문자를 소문자로 변환하고 영숫자가 아닌 모든 문자를 제거한 후 앞뒤로 동일하게 읽는 경우 구문은 회문입니다. 영숫자 문자에는 문자와 숫자가 포함됩니다.
문자열 s가 주어지면 회문이면 true를 반환하고 그렇지 않으면 false를 반환합니다.

 

 

Constraints:

 

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

---

STEP 2. 'Valid Palindrome' 코드(code)

 

■ Runtime: 47ms Beats 45.32%
■ Memory: 17.97MB Beats 23.02%

 

import re
class Solution:
    def isPalindrome(self, s: str) -> bool:
        s_foreward = ''.join(re.findall('[0-9a-z]', s.lower()))

        # If s is empty string, then return True
        if len(s_foreward)==0 : return True

        s_backward = s_foreward[::-1]
        
        return True if s_foreward == s_backward else False

 

---

STEP 3. 'Valid Palindrome' 해설

 

알파벳 + 숫자 데이터 (alphanumeric data)에 대해서 좌우 반전하여도 일치하는 경우 (palidrome)면 True, 아니면 False를 반환합니다. 이를 위해 정규 표현식을 적용하도록 re 라이브러리로 활용하였습니다.

 

또한 빈 문자열인 경우에는 True를 먼저 반환하도록 처리하고, 좌우 반전을 판단하도록 적용했습니다.

 

 

STEP 4. 'Valid Palindrome' solution

 

추가적으로, Leetcode에서 제공해준 solution 코드를 살펴보겠습니다.

파이썬 내장 함수인 isalnum은 alphanumeric을 판단합니다. 또한 two point method를 적용하여 left, right의 일치 여부를 판단하였습니다.

 

■ Runtime: 36ms Beats 93.26%
■ Memory: 16.91MB Beats 84.64%

 

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

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

---

■ 마무리

 

오늘은 Leetcode 알고리즘 문제 '125. Valid Palindrome'에 대해서 알아봤습니다.

좋아요와 댓글 부탁드리며,

오늘 하루도 즐거운 날 되시길 기도하겠습니다 :)

감사합니다.