[문자열 조작] 유효한 팰린드롬

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

 

예제 1

# 입력
"A man, a plan, a canal: Panama"

# 출력
true

 

예제 2

# 입력
"race a car"

# 출력
false

---

풀이 1. 리스트로 변환

def isPalindrome(self, s: str) -> bool:
    """
    전처리
    """
    strs = []
    for char in s:
        if char.isalnum(): # 영문자, 숫자만을 대상
            strs.append(char.lower()) # 대소문자 구문 없으므로 소문자로 변환

    # -> strs = ['a', 'm', 'a', 'n', 'a', 'p', 'l', 'a', 'n', 'a', 
    #            'c', 'a', 'n', 'a', 'l', 'p', 'a', 'n', 'a', 'm', 'a']

    """
    팰린드롬 판별
    """
    while len(strs) > 1: # 리스트의 모든 원소 비교
        if strs.pop(0) != strs.pop(): # pop() 함수는 인덱스 지정이 가능하여 이처럼 맨앞과 맨뒤를 비교
            return False # 값이 서로 다르면 팰린드롬이 아니기 때문에 False 리턴
    
    return True # 모든 값이 같으면 팰린드롬으로 판단하여 True 리턴
        

 

풀이 2. 데크 자료형을 이용한 최적화

def isPalindrome(self, s: str) -> bool:
	# 데크 자료형으로 선언
    strs: Deque = collections.deque()
    
    for char in s:
    	if char.isalnum():
        	strs.append(char.lower())
            
    # 리스트의 pop(0)은 O(n)인 데 반해, 데크의 popleft는 O(1)이기 때문에 이전 풀이와
    # 성능을 비교했을 때 속도를 훨씬 높일 수 있다.
    while len(strs) > 1:
    	if strs.popleft() != strs.pop():
        	return False
   
    return True

 

풀이 3. 슬라이싱 사용

def isPalindrome(self, s: str) -> bool:
	s = s.lower()
	s = re.sub('[^a-z0-0]', '', s) # 정규식으로 불필요 문자 필터링
    
	# 슬라이싱으로 s[::-1]으로 문자열 리스트를 뒤집을 수 있기 때문에 아래와 같이
	# 간편하게 비교가 가능하다. (슬라이싱은 C로 빠르게 구현되어 훨씬 더 빠르다)
	return s == s[::-1]