Problem

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

example

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

solution

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # Palindrome Discrimination and Two-Pointer Extension
        def expand(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]
        
        # Return quickly when not applicable
        if len(s) < 2 or s == s[::-1]:
            return s
        
        result = ''
        # Slide window to the right
        for i in range(len(s) - 1):
            result = max(result,
                        expand(i, i + 1), # odd pointer
                        expand(i, i + 2), # even pointer
                        key = len)
        return result

• 홀수 / 짝수 포인터를 이용하여 다이나믹 프로그래밍 하여 문제를 푸는 방법이다.