[LeetCode] Valid Palindrome

leetcode.com/problems/valid-palindrome/

Valid Palindrome - LeetCode

 

(0) 맨 처음에 내가 작성했던 코드

class Solution:
    def isPalindrome(self, s: str) -> bool:
        
        # filter only alphabets & make all of them in lower case
        s = s.lower()
        filtered = [v for v in s if v.isalpha() or v.isdigit()]
        
        length = len(filtered)
        # base case
        if length<=1:
            return True
        
        # non-base case
        iter_num = length//2
        for i in range(iter_num):
            if (filtered[i] != filtered[length-1-i]):
                return False
        
        # if suceessfully finished the for loop, return True
        return True

 

 

 

 

 

(1) <파이썬 알고리즘 인터뷰> : 리스트 변환

=> 나랑 다른점 :

(1) s.isalnum() 이라는 메소드를 사용해 alphabet +number 인지 아닌지를 한큐에 바로 판단.

(2) pop을 통해 맨 앞과 맨 뒤를 각각 pop해가면서 비교 후 삭제하는 방법을 사용함.

 

def inPalindrome(self, s: str) -> bool:

    # (1) 전처리
    strs = []
    for char in s:
    	if char.isalnum():
        	strs.append(char.lower())
            
    # (2) 팰린드롬 여부 판별
    while len(strs) > 1:
    	if strs.pop(0) != strs.pop():
        	return False
    
    return True

 

 

(2) <파이썬 알고리즘 인터뷰> :  deque 자료형을 이용한 최적화

-> 리스트 만으로 문제해결이 가능하기는 하지만, 데크 자료형을 이용하면 속도를 좀더 높일 수 있음.

 

def inPalindrome(self, s: str) -> bool:
    
    # (1) deque로 자료형 선언
    strs: Deque = collections.deque()
   
    for char in s:
    	if char.isalnum():
        	strs.append(char.lower())
            
    # (2) 팰린드롬 여부 판별
    while len(strs) > 1:
    	if strs.popleft() != strs.pop():
        	return False
    
    return True

 

-> 리스트의 pop(0)은 O(n)이 소요되는데 데크의 popleft()는 O(1)이므로 앞의 풀이에 비해 거의 5배 가까이 속도를 높일 수 있음.

 

 

(3) <파이썬 알고리즘 인터뷰> : 슬라이싱 사용

 

=> 정규식으로 불필요한 문자를 필터링하고, 문자열을 조작할 수 있는 파이썬의 슬라이싱을 사용

=> 파이썬에서는 [::-1]을 이용하면 문자열, 배열 등의 순서를 뒤집을 수 있음.

=> 슬라이싱은 내부적으로 C로 빠르게 구현되어있기 때문에 훨씬 더 좋은 속도를 기대할 수 있음.

=> (2)번 풀이에 비해 2배가량 더 속도를 높일 수 있음.

 

def inPalindrome(self, s: str) -> bool:

    s = s.lower()
    
    # 정규식으로 filter 작업 진행
    s = re.sub('[^a-z0-9]', '', s)
    
    return s == s[::-1] # 슬라이싱

 

 

 

 

 

 

** 인사이트

* 파이썬에서의 문자열 슬라이싱

-> 위치를 지정하면 해당 위치의 배열 포인터를 얻게 되며 이를 통해 연결된 객체를 찾아 실제 값을 알아내는데,

이 과정이 매우 빠르게 진행되므로 문자열을 조작할 때는 항상 슬라이싱을 우선으로 사용하는 편이 속도 개선에 유리.

 

(문자열을 별도로 리스트로 매핑하는 등의 처리는 별도 자료형으로 매핑하는 과정에서 상당한 연산비용이 필요하므로 전체적인 속도에서는 오히려 손해를 볼 수 있음.)

=> 따라서, 대부분의 문자열 작업은 슬라이싱으로 처리하는 편이 가장 빠름.

 

 

 

 

[ 참고 ] 

s[:]

>> 사본을 return.

참조가 아닌 값을 복사하기 위해 [:]을 사용할 수 있으며,

이 방식은 문자열이나 리스트를 복사하는 파이썬다운 방식이기도 함!

 

s[::-1]

>> 뒤집는다.

 

s[::2]

>> 두칸씩 뛰어넘어서 반환함.

s = "안녕하세요"
print(s[::2])
>> 안하요

 

---

내용 참고 및 출처 : 

 

책 <파이썬 알고리즘 인터뷰>