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

문제

가장 긴 팰린드롬 부분 문자열을 출력하라

 

· 입출력 예 

s	return
"babad"	"bab"
"cbbd"	"bb"

---

풀이

1. 중앙을 중심으로 확장하는 풀이

-> 이 문제는 다이나믹 프로그래밍으로도 풀 수 있지만, 이를 이용한 풀이는 직관적으로 이해하기 어렵고, 실행 속도가 늦다. 이에 투포인터가 중앙을 중심으로 확장하는 형태로 문제를 풀어보자.

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

가장 먼저 리스트 슬라이싱을 이용한 예외 처리를 해줌으로써 전체적인 풀이 속도를 향상한다. 이후 슬라이딩 윈도우가 문자열 처음부터

끝까지 우측으로 이동하며, expand()로 정의한 중첩 함수에서 홀수 (i, i+2), 짝수 (i, i+1)의 투 포인터가 팰린드롬 여부를 판별하며 최대값을 구한다.

---

Info

1. max 함수를 사용할 때 key 값을 설정해주면, 대상이 문자열이라도 key 값을 기준으로 최댓값을 구할 수 있다.