[python] 125. Valid Palindrome

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

Valid Palindrome - LeetCode

주어진 문자열이 펠린드롬인지 확인하는 문제
대소문자를 구분하지 않고, 알파벳과 숫자만을 대상으로 한다. 

---

풀이 1.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = ''.join(char for char in s if char.isalpha()).lower()
        new_s = s[::-1]
        if s == new_s:
            return True
        else:
            return False

 

join과 슬라이싱 그리고 리스트 컴프리헨션을 활용하여 문제를 풀었다. 

(결과)
input : "0P"
output: True
expected: False

숫자도 남겨야 하는데 문제를 제대로 읽지 않아 조건을 맞추지 못했다. 

(수정)
s = ''.join(char for char in s if char.isalpha() or char.isnumeric()).lower()

(결과) 
Runtime: 47 ms, faster than 87.90% of Python3 online submissions for Valid Palindrome.

 

풀이 2.

# 정규식 사용 
import re
class Solution:
    def isPalindrome(self, s: str) -> bool:
        s = s.lower()
        s = re.sub(r"[^a-z0-9]","",s)
        new_s = s[::-1]
        if s == new_s:
            return True
        else:
            return False

 

정규식을 사용하여 알파벳과 숫자만 저장하는 방식으로 문제를 풀었다. 

(결과)
Runtime: 54 ms, faster than 74.67% of Python3 online submissions for Valid Palindrome.

 

풀이 3.

class Solution:
    def isPalindrome(self, s: str) -> bool:
        new_s = []
        for a in s:
            if a.isalnum():
                new_s.append(a.lower())
        while len(new_s) > 1:
            if new_s.pop(0) != new_s.pop():
            # 한번이라도 같으면 True를 반환하기 때문에
            # == 으로 조건을 달면 안된다
                return False
        return True

 

리스트의 pop을 사용하여 문제를 풀었다. 

아래 작성한 코드처럼 pop으로 뽑힌 문자만을 비교하는 방식으로 코드를 작성하였는데 오류가 발생하였다. 

아래 코드처럼 같을 때 True를 반환한다면 

한 번이라도 같은 문자가 pop 되었을 때 True를 반환하여 원치 않는 결과를 출력하게 된다. 

위의 코드처럼 != 를 사용하여 코드를 수정하면 된다. 

 

if new_s.pop(0) == new_s.pop():
	return True
else: 
	return False

 

(결과)
Runtime: 288 ms, faster than 5.03% of Python3 online submissions for Valid Palindrome.

 

풀이 4.

# deque 이용 
import collections
class Solution:
    def isPalindrome(self, s: str) -> bool:
        strs: Deque = collections.deque()

        for a in s:
            if a.isalnum():
                strs.append(a.lower())

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

 

deque를 사용하여 문제를 풀었다. 

deque를 사용하기 위해서는 collections를 import 해야 한다. 

풀이 3번과 유사한 코드이지만

deque를 선언하고 popleft, pop을 사용하여 실행 시간을 줄일 수 있었다. 

(결과)
Runtime: 66 ms, faster than 54.92% of Python3 online submissions for Valid Palindrome.