[LeetCode] 5. 가장 긴 팰린드롬 부분 문자열(Longest Palindrom Substring)

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

Input: s = "babad"

Output: "bab"

Note: "aba" is also a valid answer.

 

내가 직접 푼 코드

 

,,,

 

해설 :

 

아쉽게도 없다...

나는 이 문제를 풀지 못했기 때문이다.

우선 나는 처음에 홀수 팰린드롬만 생각하고 코드를 짰다.

하지만 아쉽게도 팰린드롬은 bb와 같이 짝수인 경우도 있다.

그리고 무엇보다 s [::-1]을 응용하여 역순과 정순을 비교하여 팰린드롬을 찾으려 했지만

초반부에 s[0:-1:-1]이 계산이 안돼서 깔끔하게 만들지 못할 것 같아 3시간 고민하고 gg...

 

 

** 깔끔한 답안 **

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

 

class Solution:
    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

 

 

 

 

 

 

 

출처 : 파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]