[python3] 516. Longest Palindromic Subsequence

풀이 일자: 23.04.14

난이도: [Medium]

분류: [DP]

문제 내용

s가 주어졌을 때 해당 s의 subsequence 중 가장 긴 회문의 길이를 구하는 문제이다.

 

subsequences > 0개 이상의 원소를 삭제함으로써 반들어지는 substring으로 보면 된다.

회문 > 앞으로 읽어도 뒤로 읽어도 똑같은 것을 의미한다.  ex)기러기..

 

문제 해결 흐름

1. 처음 이 문제를 보고 떠오르는 알고리즘은 two-pointer나 DP정도뿐이었다.

→ 그 이유로는 전체를 일단 쪼개서 작은 것부터 처리하고 점차 붙여나가면서 답을 만들어가는 해결방식뿐이었다.

 

dp[i][j] = i ~ j번째의 문자를 이용하여 만들 수 있는 최대 회문의 크기

dp[i][i] = i ~ i번째의 문자를 이용하여 만들 수 잇는 최대 회문의 크기 = 1

 

1) 첫 번째 경우의 수

s[i] == s[j] 

=>  dp[i][j] = dp[i+1]dp[j-1] + 2

 

만약 i번째와 j번째 문자가 같다면 (i+1)~(j-1)번째 문자를 이용하여 만들 수 있는 최대 회문의 크기에 2를 더한다.

=> 2를 더하는 이유는 i번째와 j번째도 회문의 일부가 될 수 있기 때문..

 

2) 두 번째 경우의 수

s[i] != s[j]

=>  dp[i][j] = max(dp[i+1][j], dp[i][j-1])

 

만약 i번째와 j번째 문자가 같지 않다면 현재의 i와 j는 동시에 회문의 일부가 될 수가 없다는 의미이다.

=> 따라서 dp[i][j-1](i를 포함하고 j를 포함하지 않은 경우)와 dp[i+1][j](i를 포함하지 않고 j를 포함했을 경우)의 max로 결정

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s);
        dp = [[0 for i in range(n)] for _ in range(n)];
        ans = 0;

        for i in range(n - 1, -1, -1):
            dp[i][i] = 1;
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    dp[i][j] = 2 + dp[i+1][j-1];
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        return dp[0][n-1];

 

Time Complexity:  O(N^2)

시간복잡도는 i와 j라는 two pointer를 이용하여 시작과 끝을 지정해주기 때문에 N^2의 시간복잡도를 가질 것이다.

 

Space Complexity: O(N^2)

dp라는 메모리제이션을 위한 공간을 만들었기 때문에 공간복잡도는 N^2을 가질 것이다.

 

=> DP에서 N^2의 공간복잡도를 가진 경우 N의 공간복잡도를 가지게도 만들 수 있을 것이다.

 

다른 해결 방식

1. 앞서 언급했듯이 이를 N의 공간복잡도를 가지도록 만들 수 있는데 Official Solution에서 이를 제시했다.

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp, dpPrev = [0] * n, [0] * n

        for i in range(n - 1, -1, -1):
            dp[i] = 1
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    dp[j] = dpPrev[j - 1] + 2
                else:
                    dp[j] = max(dpPrev[j], dp[j - 1])
            dpPrev = dp[:]

        return dp[n - 1]

 

Time Complexity:  O(N^2)

시간복잡도는 i와 j라는 two pointer를 이용하여 시작과 끝을 지정해주기 때문에 N^2의 시간복잡도를 가질 것이다.

 

Space Complexity: O(N)

1차원 배열 형태의 array를 지정했기 때문에 N의 공간복잡도를 가지게 된다.

 

 

문제 링크

https://leetcode.com/problems/longest-palindromic-subsequence/description/

Longest Palindromic Subsequence - LeetCode