[파이썬 알고리즘 인터뷰][문자열] 유효한 팰린드롬

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

책에서 구현된 코드

def isPalindrome(s: str) -> bool:
    s = s.lower()
    s = re.sub('[^a-z0-9]', '', s)

    return s == s[::-1]

 

기억해야할 기법

• isalnum(), isalpha()
  
  • 알파벳인지, 숫자인지 등등을 확인해주는 내장함수가 있음
• re(pattern, replace, str)
  
  • str에서 pattern을 찾아 replace로 바꿈
  • re.sub('[^a-z0-9]', '', s)
    - 알파벳 소문자와 숫자가 아닌 것은 삭제
    - [] 중에 하나
    - ^는 not
• 문자 뒤집기
  
  • [::-1]이 reverse보다 빠름
  • [시작인덱스 : 끝인덱스 : 다음인덱스에 더할 값]

 

내가 구현한 코드

def valid_palindrome(string:str):
    left, right = 0, len(string) - 1
    string = string.lower()

    while True:
        # skip non-alphabet & non-digit in range
        while not string[left].isalnum() and left <= len(string) - 1:
            left = left + 1
        while not string[right].isalnum() and right >= 0:
            right = right - 1

        # check if the both of pointers have been reached
        if left >= right:
            break

        # check if is valid palindrome
        if string[left] != string[right]:
            return False

        # move to next char to compare
        left = left + 1
        right = right - 1

    return True

• 문자열 자체에 대한 변형이 없으므로 속도는 내가 작성한 코드가 빠름

• 그러나 라인수와 가독성이 비교가 안됨 -> 가독성을 고려할 수 있는 함수들을 최대한 생각해낼것
• 반환값 타입 명시할 것

 

+) Leetcode에 제출해보면서 잘못된 부분 수정

class Solution:
    def isPalindrome(self, string:str):
        left, right = 0, len(string) - 1
        string = string.lower()

        while True:
            # skip non-alphabet & non-digit in range
            while left <= len(string) - 1 and not string[left].isalnum():
                left = left + 1
            while right >= 0 and not string[right].isalnum():
                right = right - 1

            # check if the both of pointers have been reached
            if left >= right:
                break

            # check if is valid palindrome
            if string[left] != string[right]:
                return False

            # move to next char to compare
            left = left + 1
            right = right - 1

        return True

• 수정한 부분
  • left와 right를 옮기는 while의 두 조건 위치를 바꿈
    - 범위 조건에 맞지 않을 경우, string[left]/right]에서 인덱스