[LeetCode] 125. Valid Palindrome (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.

Example 1:

Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

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

LeetCode 125. Valid Palindrome (유효한 팰린드롬)

문자열이 팰린드롬(회문) 인지 판별하는 문제
단, 단순히 문자열을 뒤집어 비교하는 게 아니라 다음 조건을 적용

대문자는 소문자로 변환
영문/숫자(알파벳+숫자)만 남기고 나머지 문자(공백, 쉼표, 콜론 등)는 제거
정제된 문자열이 앞에서 읽으나 뒤에서 읽으나 같으면 True, 아니면 False

예를 들어
"A man, a plan, a canal: Panama" → "amanaplanacanalpanama" 이므로 팰린드롬

✔풀이

from collections import deque

class Solution:
    def isPalindrome(self, s: str) -> bool:
        dq = deque()

        for char in s:
            if char.isalnum():
                dq.append(char.lower())

        while len(dq) > 1:
            if dq.popleft() != dq.pop():
                return False 
        return True

문제 해결의 핵심은 문자열 전처리와 양끝 비교 방식
문자열을 한 번 순회하면서 유효한 문자만 수집한 뒤, 앞과 뒤의 문자를 동시에 비교하는 접근 방식

이 과정에서 deque 자료구조를 사용하는 이유는 다음과 같음

양쪽 끝에서의 삽입 및 삭제가 O(1)인 자료구조
양끝 비교 로직 구현에 적합한 구조
불필요한 인덱스 계산이 없는 직관적인 구현 가능성
리스트를 사용하지 않아도 됨!

✔최적화

import re

class Solution:
    def isPalindrome(self, s: str) -> bool:
        filtered = re.sub(r'[^a-zA-Z0-9]', '', s).lower()
        return filtered == filtered[::-1]

슬라이싱해서 속도를 줄일 수 있는 방법을 알게 됨
filtered = re.sub(r'[^a-zA-Z0-9]', '', s).lower()
- 문자열 s에서 알파벳과 숫자가 아닌 모든 문자를 제거
- 남은 문자를 전부 소문자로 변환한 결과를 filtered에 저장
filtered[::-1]를 통한 회문 비교

💡문자열 슬라이싱

파이썬에서 문자열을 조작할 때는 슬라이싱을 우선으로 사용하는 편이 속도 개선에 유리
문자열을 별도로 리스트로 매핑하는 등의 처리는 데이터 구조를 다루는 입장에서 좋음
- 하지만 별도 자료형으로 매핑하는 과정에서 상당한 연산 비용이 필요
- 전체적인 속도에서 손해를 볼 수 있음
대부분의 문자열 작업은 슬라이싱으로 처리하자 !
s[:]: 사본을 리턴
- 참조가 아닌 값을 복사하기위해 [:]를 사용할 수 있음
s[::-1]: 해당 문자열을 뒤집기

LeetCode 125. Valid Palindrome (유효한 팰린드롬)

문자열이 팰린드롬(회문) 인지 판별하는 문제
단, 단순히 문자열을 뒤집어 비교하는 게 아니라 다음 조건을 적용

대문자는 소문자로 변환

영문/숫자(알파벳+숫자)만 남기고 나머지 문자(공백, 쉼표, 콜론 등)는 제거

정제된 문자열이 앞에서 읽으나 뒤에서 읽으나 같으면 True, 아니면 False

예를 들어
"A man, a plan, a canal: Panama" → "amanaplanacanalpanama" 이므로 팰린드롬

✔풀이

from collections import deque class Solution: def isPalindrome(self, s: str) -> bool: dq = deque() for char in s: if char.isalnum(): dq.append(char.lower()) while len(dq) > 1: if dq.popleft() != dq.pop(): return False return True

이 과정에서 deque 자료구조를 사용하는 이유는 다음과 같음

양쪽 끝에서의 삽입 및 삭제가 O(1)인 자료구조

양끝 비교 로직 구현에 적합한 구조

불필요한 인덱스 계산이 없는 직관적인 구현 가능성

리스트를 사용하지 않아도 됨!

✔최적화

import re class Solution: def isPalindrome(self, s: str) -> bool: filtered = re.sub(r'[^a-zA-Z0-9]', '', s).lower() return filtered == filtered[::-1]

슬라이싱해서 속도를 줄일 수 있는 방법을 알게 됨

filtered = re.sub(r'[^a-zA-Z0-9]', '', s).lower()

문자열 s에서 알파벳과 숫자가 아닌 모든 문자를 제거
남은 문자를 전부 소문자로 변환한 결과를 filtered에 저장

filtered[::-1]를 통한 회문 비교

💡문자열 슬라이싱

파이썬에서 문자열을 조작할 때는 슬라이싱을 우선으로 사용하는 편이 속도 개선에 유리

문자열을 별도로 리스트로 매핑하는 등의 처리는 데이터 구조를 다루는 입장에서 좋음

하지만 별도 자료형으로 매핑하는 과정에서 상당한 연산 비용이 필요
전체적인 속도에서 손해를 볼 수 있음

대부분의 문자열 작업은 슬라이싱으로 처리하자 !

s[:]: 사본을 리턴

참조가 아닌 값을 복사하기위해 [:]를 사용할 수 있음

s[::-1]: 해당 문자열을 뒤집기