LeetCode [125]: Valid Palindrome

📌 LeetCode [125]: Valid Palindrome

🔗 문제 링크

---

문제 설명 📄

문자열 s가 주어질 때, 영문자와 숫자만 고려하여 대소문자를 구분하지 않고 회문인지 확인하는 문제입니다.

---

문제 접근 방식 📋

1. 영숫자 필터링:
   • 문자열에서 영문자(a-zA-Z)와 숫자(0-9)만 남기고, 다른 문자를 제거합니다.
   • 이 과정에서 대소문자 구분을 없애기 위해 모든 문자를 소문자로 변환합니다.
2. 회문 확인:
   • 문자열을 뒤집은 결과(s[::-1])가 원래 문자열과 같은지 비교하여 회문 여부를 확인합니다.

---

Solution 💻

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = "".join([i.lower() for i in s if i.isalnum()])

        return s == s[::-1]

시간 복잡도 분석 ⏲️

• 영숫자 필터링: O(n)
  • 문자열 길이가 n일 때, 모든 문자를 순회하며 조건을 검사.
• 회문 확인: O(n)
  • 문자열을 뒤집어 비교.
• 총 시간 복잡도: O(n)

---

리팩토링 🛠️

개선된 코드

import re

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

        left, right = 0, len(s) - 1
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1

        return True

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 두 포인터가 문자열을 한 번 순회.
• 공간 복잡도: O(1)
  • 문자열을 뒤집지 않으므로 추가 메모리 사용을 줄임.