[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:

1
2

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

Example 2:

1
2

Input: "race a car"
Output: false

Constraints:

• s consists only of printable ASCII characters.

Valid Palindrome 문제 풀이

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

  • 예시: 다시 합창합시다 -> 다시합창합 시다
  • 예시: race car -> rac ecar

• 문제의 중요한 조건은 대소문자를 구분하지 않는다고 합니다. 문제 풀이의 편의를 위해 모두 소문자로 변경하도록 합니다.

첫 번째 방법

• 리스트를 사용한 간단한 풀이방법 입니다.
• 문자열을 문자 하나씩 잘라내어 list()로 변환하고, 리스트의 시작과 끝을 시작으로 하나씩 비교하는 방법입니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

두 번째 방법

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

1
2
3
4
5
6
7
8

import re

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

        return s == s[::-1]