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

 

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

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

예제1
* 입력
"babad"
* 출력 
"bab" 


예제2
* 입력 
"cbbd"
* 출력 
"bb"

 

# 슬라이딩 윈도우 

# 팰린드롬 판별 및 투 포인터 확장 
def expand(s,left:int, right: int) ->str:
    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 

s="cbbd"
result = ""
# 슬라이딩 윈도우 우측으로 이동 
for i in range(len(s)-1):
    result = max(result, expand(s, i, i+1), expand(s, i, i+2), key = len)
result 
>>> "bb"