문제

Given a string s, return the longest palindromic substring in s.
s라는 문자열이 주어질 때 가장 긴 팰린드롬 부분 문자열을 찾아라.

예시 입력

babad

예시 출력

bab (혹은 aba)

풀이 방법

보통 하나의 문자열 안에서 특정 조건을 충족하는 문자열인 경우 투 포인터를 사용하는 경우가 많았다.

따라서 이번 문제에서도 투 포인터를 사용하려고 시도했다.
투 포인터를 사용한다는 것은 작은 부분에서 시작해 길이를 늘려가는 것이 핵심이라고 할 수 있다. 따라서 가장 작은 Palindrome에 대해 생각해보았고 두 가지의 가장 작은 Palindrome이 존재할 수 있음을 알았다.

1. 길이가 1인 문자열 (예: b)
2. 길이가 2인 문자열 (예: bb)

이 두가지의 가장 작은 팰린드롬으로 시작하여 투 포인터로 확장하면 된다.

제출 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        """
        1. expand 함수를 정의한다.
            - expand함수는 left, right를 인자로 받고, 값이 같을 때까지 계속 left--, right++를 진행한다.
            - 값이 다르거나 범위를 벗어나면 s[left+1:right-1]을 반환한다.
        2. s를 순환하면서 최대 palindrom 문자열 길이를 비교한다.
        """
        def expand(left: int, right: int) -> str:
            while 0 <= left and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left+1:right]
        
        if len(s) <= 1 or s == s[::-1]:
            return s
        
        longest_palindrom = ''
        for i in range(len(s) -1):
            longest_palindrom = max(longest_palindrom, expand(i, i), expand(i, i + 1), key=len)
        return longest_palindrom

제출 결과