[Python] 문자열 조작 4 <가장 긴 팰린드롬 부분 문자열>

단순 문자열 조작 파트의 마지막 문제이다. 입력으로 어떤 문자열이 주어졌을 때, 해당 문자열에서 가장 긴 부분 팰린드롬을 찾으라는 문제이다.

입출력 예제는 다음과 같다.

---

 

 

---

문제는 두개의 포인터가 중앙을 중심으로 확장하는 형태로 풀 수 있다. 두개의 포인터는 처음엔 문자열 2자리, 3자리로 작은 규모로 시작하여 팰린드롬을 발견했을 때, 중앙을 중심으로 이를 확장하는 방식이다.

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

    # 길이가 2보다 작거나, 뒤집은 값이 동일하다면 빠르게 리턴
    if len(s) < 2 or s == s[::-1]:
        return s

    result = ''
    for i in range(len(s) - 1):
        # max(iterable, *args, key=function) key 가 들어갔을 때는 key 를 기준으로 찾는다.
        # 결과 값은 iterable   이 가진다.
        result = max(result,
                    expand(i, i+1), # 짝수 포인터
                    expand(i, i+2), # 홀수 포인터
                    key=len)
    return result


if __name__ == '__main__':
    s = "babad"
    print(longestPalindrome(s))

---