06. 가장 긴 팰린드롬 문자열(leetcode: 5)

문제링크

문제 분석

해당 문제는 주어진 문자열에서 가장 긴 팰린드롬을 찾는 문제.

풀 수 있는 방법으로는 두 개의 포인터를 이용해서 늘려나가는 투 포인터 기법 있다.

문제를 보자마자 생각이 나긴했지만, 투 포인터를 어떻게 적용해야 하는지에 대한 감이 오지 않았다. 어려웠던 부분은

1. 팰린드롬의 길이가 짝수일 수도, 홀수일수도 있는데 이걸 어떻게 만들어야할까였다.

2. 주어진 문자열의 길이가 1일 때는 깔끔하게 처리하기

위의 문제를 고민하다가 해설을 봤고 해설에서는 위의 두 문제를 아주 깔끔하게 정리했다.

1. 투 포인터 기법을 두개로 만들어서 하나는 짝수, 하나는 홀수의 경우로 나눠서 분석한다.

2. 메인 로직을 실행하기 전에 리턴해버린다.

풀이

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left, right):
            while left >= 0 and right <= len(s) - 1 and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left + 1:right]
        if len(s) < 2 or s == s[::-1]:
            return s
        ret = ''
        for i in range(len(s)):
            ret = max(ret,
                     expand(i, i + 1),
                     expand(i, i + 2),
                     key=len)
        return ret