[알고리즘] 가장 긴 팰린드롬 부분 문자열

[가장 긴 팰린드롬 부분 문자열]

내 풀이

def longestPalindrome(s:str)-> str:
    longest_word = s[0]
    for i in range(0,len(s)-1):
        for j in range(i, len(s)):
            if s[i:j+1] == s[i:j+1][::-1] and j-i+1 > len(longest_word):
                longest_word = s[i:j+1]
    return longest_word

O(n^2) 방식으로 풀어서 시간 초과가 났다.

책 풀이

def longestPalindrome(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

max 함수를 사용할 때, key를 설정하여 비교 기준을 결정할 수 있다.