파이썬 알고리즘 인터뷰 - 06. 가장 긴 팰린드롬 부분 문자열

 

<--- 리트코드 5. Longest Palindrome Substring ---> 

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

 

입력

"babad"

출력

"bab"

 

입력

"cbbd"

출력

"bb"

 

 

# 풀이

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

def longest_palindrome(s):
    # 팰린드롬 판별 및 투 포인터 확장
    def expand(left, right):
        while left >= 0 and right <= len(s) and s[left] == s[right-1]:
            left -= 1
            right += 1
        return s[left + 1:right -1]
 
    # 해당 사항이 없을 때 빠르게 리턴
    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
 
s = input()
print(longest_palindrome(s))