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

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브

 

---

6. 가장 긴 팰린드롬 부분 문자열

리트코드 5번 문제입니다.

leetcode.com/problems/longest-palindromic-substring/

 

풀이

 팰린드롬은 홀수, 짝수 펠린드롬으로 나눠서 생각해 볼 수 있습니다.

 

 책에서는 홀수, 짝수 펠린드롬을 각각 판별하도록 풀어냈습니다.

 

 펠린드롬을 판별하는 함수를 정의하고 홀수, 짝수 펠린드롬을 문자열 처음부터 판별해나갑니다.

 

 max 함수에 key 인자를 len으로 입력하여 문자열 길이를 기준으로 최대값을 취할 수 있다는 것을 배웠습니다.

 

def longestPalindrome(self, s):
    # 팰린드롬 판별 및 투 포인터 확장
    def expand(left, right):
        while left >= 0 and right <= len(s) and s[left] == s[right-1]:
            left -= 1
            right += 1
        return s[left + 1:right -1]

    # 해당 사항이 없을 때 빠르게 리턴
    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