[파이썬 알고리즘 인터뷰][문자열] 가장 긴 팰린드롬 부분 문자열

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

---

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

 

책에서 구현된 코드

def longestPalindrome(self, s:str) -> str:
        def expand(left: int, right: int) -> str:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left+1:right]

        if len(s) < 2 or s == s[::-1]:
            return s

        result = ''
        for i in range(len(s)-1):
            result = max(result, expand(i, i+1), expand(i, i+2), key=len)

        return result

 

기억해야할 기법

• 슬라이딩 윈도우 방식
  
  • 슬라이딩 윈도우 방식으로 전체탐색
• 예외처리
  • 예외처리에서 s[::-1]를 추가할 생각을 못함
• 문제의 이해
  • 무엇보다 중요한 것인데, 부분 팰린드롬임을 인지하지 못함

 

내가 구현한 코드

def longest_palindrome(s:str) -> str:
    left, right = 0, len(s) - 1
    start, length = 0, 1
    results = []

    if len(s) == 1:
        return s

    while left <= right:
        if s[left] == s[right]:
            length = length + 1

        else:
            results.append(s[start:start+length])
            start, length = left+1, 1

        left, right = left+1, right-1

    if length > 1:
        results.append(s[start:start + length])

    return max(results, key=lambda x: len(x))

• 홀수일 경우, 가운데 값이 같을 때 로직
  ex) "ccd"가 input일 경우
  -> "cd"가 출력됨
  1) 가운데에서 left와 right가 같다고 판단
  2) length를 ++하고 while문을 마침
  3) length > 1에서 "cd"를 append
• left만 같은 char로 반복되는 case (부분 팰린드롬을 고려하지 않음)