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

테스트 케이스 1)

- 입력 : "babad"

- 출력 : "bab" 

- 설명 : "bab" 외에 "aba" 도 정답이다.

 

테스트 케이스 2)

- 입력 : "cbbd"

- 출력 : "bb"

 

- 앞뒤로 똑같은 단어를 찾는것  토마토, 기러기 이렇게..

- 그중에서 제일 긴 값을 찾는 것

 

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

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