[Leetcode]125. Valid Palindrome

📄 Description

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.

주어진 문자열이 팰린드롬인지 확인하라. 대소문자를 구분하지 않으며, 영문자와 숫자만을 대상으로 한다.

❓ Palindrome?

앞뒤가 똑같은 단어나 문장으로, 뒤집어도 같은 말이 되는 단어 또는 문장을 팰린드롬(Palindrome)이라고 한다.

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 * 10^5$
• s consists only of printable ASCII characters.

💻 My Submission

class Solution:
    def isPalindrome(self, s: str) -> bool:
        
        strs=[]
        
        for char in s:
            if char.isalnum():
                strs.append(char.lower())
        
        if strs==strs[::-1]: return True
        return False

🔨 My solution

📌 1) s에서 영문자와 숫자만 추출한다.

👉 방법 1: isalnum() 사용

💡 isalnum()

영문자, 숫자 여부를 판별하는 함수로, 이를 이용해 해당하는 문자만 추출한다.

👉 방법 2: 정규표현식 사용

💡 re.sub()

re.sub(정규표현식, new_text, text)

• text에서 정규표현식에 맞는 부분을 new_text로 대체하라는 의미.

📌 2) 팰린드롬인지 확인한다.

👉 방법 1: 슬라이싱

• arr[::-1] - 리스트를 뒤집는다.

if strs!=strs[::-1]: return False

References

• https://leetcode.com/problems/valid-palindrome/
• 파이썬 알고리즘 인터뷰(95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트), 박상길 지음

👉 방법 2: List 사용

while len(strs)>1:
	if strs.pop(0)!=strs.pop(): return False

👉 방법 3: Deque 사용하여 최적화

strs: Deque = collections.deque()

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

🚩 속도 성능 개선?

List 의 pop(0) - $O(n)$ vs Deque 의 popleft() - $O(1)$
따라서 각각 $n$번씩 반복하면
List 의 pop(0) - $O(n^2)$ vs Deque 의 popleft() - $O(n)$

즉, 성능 차이가 크다!