[LeetCode] 125. Valid Palindrome - Python

MinWoo Park·2021년 4월 3일

algorithm

Algorithm

목록 보기

26/42

Algorithm Problem with Python — 26day

문제 설명 📖

Given a string s, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

제한사항

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

입출력 예

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.

문제 이해 🔑

palindrome(펠린드롬)은 우리말로 회문이라 부르며 앞뒤가 똑같은 단어나 문장을 말합니다.

주어진 문자열이 펠린드롬인지 확인하기 위해서는 문자열의 맨 앞과 맨 뒤에 각각 접근할 수 있어야 합니다.
그리고 비교할 수만 있다면 해결할 수 있는 문제입니다.

앞 뒤로 값을 접근할 때 유용한 자료형에 Deque(데크)가 있습니다.
리스트의 pop(0)이 O(n)인 데 반해, 데크의 popleft()는 O(1)이기 때문에 각각 n번씩 반복하면 리스트 구현은 O(n²), 데크 구현은 O(n)으로 성능 차이가 큽니다.

데크 자료형을 사용할 수 있는지도 체크하는 문제가 되겠습니다.

수도 코드 ✍️

데크 자료형을 만듭니다.
주어진 문자열을 for in문을 통해 순회합니다.
문자열의 각 문자가 영숫자 문자라면 데크 자료형에 소문자화 하여 값을 넣습니다.
인풋 문자열을 소문자화 하여 영숫자만 선별하였다면 펠린드롬 여부를 검사해야 합니다.
이 때 while문을 통해 데크의 길이가 1보다 큰 경우의 반복문을 만듭니다.
3번에서 만든 데크를 popleft()와 pop()을 통해 앞, 뒤 문자를 비교합니다.
모두 같다면 True, 도중에 다르다면 False를 리턴합니다.

코드 작성 ⌨️

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