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

리트코드 5. Longest Palindrome Substring

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

• 예제 1
  입력

  "babad"

  출력

  "bab"

  "bab" 외에 "aba"도 정답이다.

• 예제 2
  입력

  "cbbd"

  출력

  "bb"

✏️ 풀이 1: 중앙을 중심으로 확장하는 풀이

• 다이나믹 프로그래밍으로 풀 수 있는 전형적인 문제다. 그러나 이 문제의 경우 다이나믹 프로그래밍을 이용한 풀이는 직관적으로 이해가 어렵고, 무엇보다도 일반적인 예상과는 달리 실행 속도가 늦다.
• 따라서 좀 더 직관적이면서도 훨씬 더 성능이 좋은, 투 포인터가 중앙을 중심으로 확장하는 형태로 풀이해보겠다.

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), # 짝수 2개의 투 포인터
                        expand(i, i + 2), # 홀수 2개의 투 포인터
                        key=len)
    return result