[leetcode] 125. Valid Palindrome - Python

🔍 Problem

https://leetcode.com/problems/valid-palindrome/

---

📰 문제풀이

• 제한 시간: 15분
• 성공 여부: 성공

---

📃 Solving Process

1. 문제의 조건에 맞게 주어진 s 문자열의 알파벳을 전부 소문자로 바꾼다.
2. 알파벳이나 숫자가 아닌 특수문자를 전무 지워주기 위해 re.sub 기능을 이용해 전처리한다.
3. 전처리가 완료된 문자열이 팰린드롬인지 확인한다.

---

💻 Code

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        s = re.sub(r'[^a-z0-9]', '', s)
        for i in range(len(s) // 2):
            if s[i] != s[len(s) - 1 - i]:
                return False      
        return True
  

---

⏱ Time Complexity

• 전처리 된 문자열을 항상 절반의 범위만큼만 탐색하기 때문에 O(N/2) -> O(N)이다.

---

💾 Space Complexity

• 계속해서 처음 할당된 문자열 s를 사용하기 때문에 O(N)의 메모리 공간이 필요하다.