5. Longest Palindromic Substring (Two Pointers, String, Dynamic Programming)

링크 - https://leetcode.com/problems/longest-palindromic-substring/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

1) DP

우리는 길이가 작은 palindromic부터 dp에 저장함으로써 길이가 긴 palindromic의 여부를 알 수 있다. 예를 들어 abcdedcba를 보자. 이게 palindromic의 여부를 알려면 만약 bcdedcb가 palindromic이면, 앞뒤에 같은 글자 a가 들어왔으므로 이것은 여전히 palindromic이다

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False]*n for _ in range(n)]

        ans = [0, 0]
        for i in range(n):
            dp[i][i] = True
        for i in range(n-1):
            if s[i] == s[i+1]:
                dp[i][i+1] = True
                ans = [i, i+1]

        for diff in range(2, n):
            for left in range(n-diff):
                right = left + diff
                if s[left] == s[right] and dp[left+1][right-1]:
                    dp[left][right] = True
                    ans = [left, right]

        left, right = ans
        return s[left: right + 1]

Time Complexity: O(N^2)

Space Complexity: O(N^2) dp는 n*n의 크기를 가진다.

2) Expand From Center

우리는 매 인덱스마다 확장해서 확인하는 방식으로 이 문제를 풀 수 있다. 중요한점은 매 인덱스마다 홀수 개수와 짝수 개수의 글자들을 확인해야 한다는 것이다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ans = [0, 0]
        n = len(s)
        def expand(left, right):
            nonlocal ans
            while left >= 0 and right < n and s[left] == s[right]:
                left -= 1
                right += 1
            diff = right - left - 1
            if diff > ans[1] - ans[0] + 1:
                ans = [left + 1, right - 1]
            

        for i in range(n):
            expand(i, i)
            if i < n - 1 and s[i] == s[i+1]:
                expand(i, i+1)

        return s[ans[0]:ans[1]+1]

Time Complexity: O(N^2)

Space Complexity: O(1)