LeetCode 125. Valid Palindrome

Palindrome(팰린드롬)이란 어느 한 문자열을 반대로 읽어도 같은 문자열을 말한다.

풀이

배열로 변환

class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs = []
        for char in s :
            if char.isalnum():              # isalnum() : 해당 문자열이 영문자, 숫자 여부를 판별하는 함수
                strs.append(char.lower())   # 함수를 통과한다면 소문자로 변환하여 strs에 추가
        while len(strs) > 1:
            if strs.pop(0) != strs.pop():   # 0을 지정하면 맨 앞의 값을 가져와서 맨 뒤의 값과 비교
                return False                # 맨 앞과 뒤가 같지 않다면 False를 바로 반환
        return True

 

문자열 중간에 있는 공백과 특수기호를 제거하기 위해 isalnum() 함수를 사용하였다.

isalnum()은 해당 문자가 영문, 한글, 숫자라면 True, 그 외에는 False를 리턴하는 함수이다.

(isalpha()는 숫자를 제외한 영문 및 한글이라면 True, 그 외에는 False를 리턴)

 

.pop()을 이용하여 리스트에서 앞뒤로 하나씩 꺼내서 비교한다.

이때 while문을 '> 0'이 아닌 '> 1'로 한 이유는 문자열이 홀수개일 수도 있기 때문이다.

결과값1

---

배열 대신 데큐를 사용

import collections
class Solution:
    def isPalindrome2(self, s: str) -> bool:
        strs : Deque = collections.deque()      # strs를 배열이 아닌 Deque로 지정

        for char in s:
            if char.isalnum():
                strs.append(char.lower())
        while len(strs) > 1:
            if strs.popleft() != strs.pop():    # .popleft()를 통해 맨 앞의 값을 추출하여 맨 뒤의 값과 비교
                return False
        return True

배열을 사용한 풀이와 동일하나 배열대신 Deque를 사용했다는 점이 다르다.

Deque에서는 첫번째 값을 추출하기 위해 .popleft() 함수를 사용하였다.

결과값2

그 결과 시간 복잡도가 훨씬 줄어드는 것을 확인할 수 있다.

배열의 .pop(0)의 시간복잡도는 O(n^2)인데 반해, 데크의 .popleft()는 O(1)이기 때문이다.