[NeetCode 150/String Manipulation,TwoPointer] Valid Palindrome

https://neetcode.io/problems/is-palindrome

NeetCode

첫번째 방법 - String Manipulation

class Solution:
    def isPalindrome(self, s: str) -> bool:
        # 1. 알파벳과 숫자만 남기고 소문자로 변환
        filtered_s = ''.join(c.lower() for c in s if c.isalnum())
        
        # 2. 문자열을 뒤집어서 원래 문자열과 비교
        return filtered_s == filtered_s[::-1]

• isalnum() -> 문자열이 문자 혹은 숫자로 되어있으면 참 리턴, 아니면 거짓 리턴
• 시간 복잡도
  • 문자열 필터링: O(n)
  • 문자열 비교: O(n)
  • 총 시간복잡도: O(n) (입력 문자열 길이 n에 대해 선형 시간)

두번째 방법 - Two Pointers

투 포인터 (Two Pointers) 방식의 핵심 개념

• 왼쪽 포인터 (left): 문자열의 시작에서 오른쪽으로 이동
• 오른쪽 포인터 (right): 문자열의 끝에서 왼쪽으로 이동
• 목표: 두 포인터가 서로 만날 때까지 진행하면서 알파벳과 숫자만 비교
• 필요한 작업: 공백, 특수문자 등 비알파벳/비숫자 문자는 건너뛴다

class Solution:
    def isPalindrome(self, s: str) -> bool:
        left, right = 0, len(s) - 1
        
        while left < right: # left 포인터와 right 포인터가 서로 교차하지 않을 때까지 반복
            # 왼쪽 포인터 이동 (알파벳/숫자가 아닐 경우)
            while left < right and not s[left].isalnum():
                left += 1 # left를 오른쪽으로 이동시킴 -> 즉, 공백, 특수문자, 마침표 등을 건너뜀
            # 오른쪽 포인터 이동 (알파벳/숫자가 아닐 경우)
            while left < right and not s[right].isalnum():
                right -= 1 # right를 왼쪽으로 이동시킴 -> 즉, 공백, 특수문자, 마침표 등을 건너뜀
            
            # 소문자로 변환 후 비교
            if s[left].lower() != s[right].lower():
                return False
            
            left += 1
            right -= 1
        
        return True

• 시간/공간 복잡도
  • 공간복잡도: O(1) → 추가적인 문자열을 생성하지 않으므로 메모리 절약
  • 시간복잡도: O(n) → 문자열을 한 번만 순회