가장 긴 팰린드롬 부분 문자열 찾기

출처: 파이썬 알고리즘 인터뷰

 

 

문저열에서 가장 긴 팰린드롬 문자열을 찾는법.

 

1) 주어진 좌우 값을 기준으로 가장 긴 팰린드롬 찾는법

좌우가 같으면 값을 늘려감

def expaned( 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]

 

2) 범위 지정

문자열의 길이만큼 범위를 주며, 홀짝의 범위를 체크하기 위해

[i, i+1] 범위와 [i, i+2] 범위를 비교한다.

result = ''
for i in range( len(s) -1 ):
    result = max( result , expaned(i, i+1), expaned(i, i+2), key=len)

 

3) 우선 조건 확인

문자열의 길이가 1이거나 문자열이 풀 팰린드롬이면 바로 해당 문자열 리턴.

if len(s) < 2 or s == s[::-1]:
    return s

 

 

전체 소스

def longest_palindtome(s : str) -> str :
    def expaned( 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

    result = ''
    for i in range( len(s) -1 ):
        result = max( result , expaned(i, i+1), expaned(i, i+2), key=len)
    return result

print(longest_palindtome('babadasdffdsaerwr'))

 

print:

asdffdsa