[LeetCode_125] 유효한 팰린드롬

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

125번 Valid Palindrome은 주어진 문자열이 팰린드롬인지 확인하는 문제이다.

단 알파벳인것만 취급하며, 대소문자 구분 없이 모두 소문자로 바꿔서 평가함.

 

* 펠린드롬 : 앞뒤가 똑같은 단어나 문장 

 

 

# 풀이방법 1 - 단순 list와 for문으로 판별

class Solution:
    def isPalindrome(self, s: str) -> bool:
        
        check = []

        for c in s :
            if c.isalpha() or c.isdigit():
                check.append(c.lower())
    
        check_len = len(check)
       
        if check_len == 0 :
            return True
        
        for i in range(0, check_len//2 + 1):
            if check[i] != check[check_len-1-i] :
                return False
            
        return True

1. 문자열에서 한 문자씩 alpha이거나 digit인지 구분하여 배열에 저장한다.

2. 1에서 저장한 배열의 길이가 0이면 무조건 true 를 반환하도록 함

3. (핵심) 문자열의 길이의 1/2 만큼 for문을 돌며, 첫번째 글자[i]와 마지막 check_len-i번째 글자가 같은지 비교하여 다르면 false를 반환하도록 하였다.

 

 

# 풀이 방법 2 - deque를 이용하여 판별 (책 풀이 참고)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        
        check : Deque = collections.deque()

        for c in s :
            if c.isalnum() :
                check.append(c.lower())
    
        while len(check) > 1 :
            if check.popleft() != check.pop():
                return False
    
        return True

1. 알파벳인지 숫자인지 .isalnum 함수를 이용하여 확인 후 deque에 저장함 

2. deque의 길이가 1이상일 경우에만 왼쪽과 오른쪽의 문자열을 하나씩 pop하며 같은지 비교함 

 

| 핵심 |

.isalnum()

check : Deque = collections.deque()

check.popleft(), check.pop() 

 

 

# 풀이 방법 3 - 정규식과 [::-1] 이용 (책 풀이 참고)

class Solution:
    def isPalindrome(self, s: str) -> bool:
        
        s = s.lower()
        
        # 정규식 이용 
        s = re.sub('[^a-z0-9]', '', s)
        
        # 리스트 뒤집어 비교
        return s == s[::-1]

1. 소문자로 바꾼후 정규식을 용하여 불필요한 문자를 필터링함

2. [::-1]로 리스트를 뒤집어 비교한다. 

 

| 핵심 |

res.sub('[^a-z0-9]', '',s)

s[::-1]

 

 

# 결과