[LeetCode] Valid Palindrome

  • LeetCode: Valid Palindrome 알고리즘 문제 풀이입니다.
  • 본 문제는 LeetCode 홈페이지에서 직접 풀어볼 수 있습니다.

문제 설명

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

Constraints:

  • s consists only of printable ASCII characters.

Valid Palindrome 문제 풀이

  • 팰린드롬, Palindrome은 문장을 거꾸로 재배치하여도 원래 문장과 동일한 문장을 의미합니다. 단 여기서 띄어쓰기는 고려하지 않습니다. 아래 예시를 보면 쉽게 이해할 수 있습니다.

    • 예시: 다시 합창합시다 -> 다시합창합 시다
    • 예시: race car -> rac ecar
  • 문제의 중요한 조건은 대소문자를 구분하지 않는다고 합니다. 문제 풀이의 편의를 위해 모두 소문자로 변경하도록 합니다.

첫 번째 방법

  • 리스트를 사용한 간단한 풀이방법 입니다.
  • 문자열을 문자 하나씩 잘라내어 list()로 변환하고, 리스트의 시작과 끝을 시작으로 하나씩 비교하는 방법입니다.
class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = []
        for char in s:
            if char.isalnum():
                strs.append(char.lower())
        
        # check palindrome
        while len(strs) > 1:
            if strs.pop(0) != strs.pop():
                return False
        
        return True

두 번째 방법

  • 두 번째 방법은 정규표현식을 사용하여 문자와 숫자만 추출합니다.
  • 추출된 문자열과 추출된 문자열을 뒤집은 문자열을 같은지 비교하여 팰린드롬을 확인하는 방법입니다.
import re

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        s = re.sub('[^a-z0-9]', '', s)

        return s == s[::-1]