516. Longest Palindromic Subsequence ★★

516. Longest Palindromic Subsequence

 

https://youtu.be/bUr8cNWI09Q?si=5OUyGmMcZAuUGtkC

 

1) LCS로 푸는 법

원래 문자열과 뒤집은 문자열의 LCS 는 Longest Palindromic Subsequence 임

 

Palindromic string: 읽었을때, 앞으로 읽으나 뒤로 읽으나 같은 문자열

LCS(Longest Common Subsequence): 두 문자열에서 순서를 유지하면서 가장 긴 공통 부분 수열을 찾는 문제를 말합니다.

 

• 부분 수열 (Subsequence):
  • 문자열에서 몇 개의 문자를 순서를 유지하면서 선택한 부분 문자열.
  • 반드시 연속할 필요는 없지만, 문자들의 순서는 원래 문자열과 같아야 합니다.
  • 예:
    • 문자열 "ABCDEF"의 부분 수열: "ACE", "BDF", "ABC", "EF", 등.
• 공통 부분 수열 (Common Subsequence):
  • 두 문자열에서 순서를 유지하면서 공통으로 포함된 부분 수열.
  • 예:
    • 문자열 "ABCDEF"와 "AEDNEK"의 공통 부분 수열: "AE", "AD", "A", 등.
• 가장 긴 공통 부분 수열 (LCS):
  • 두 문자열의 모든 공통 부분 수열 중 가장 긴 수열.
  • 예:
    • 문자열 "ABCDEF"와 "AEDNEK"의 LCS는 "ADE".

 

class Solution:
    def longestCommonSubseq(self, s1: str, s2: str) -> int:
        # LCS 로 푸는 방법
        N, M = len(s1), len(s2)
        dp = [ [0] * (M+1) for _ in range(N+1) ]
        for i in range(N):
            for j in range(M):
                if s1[i] == s2[j]:
                    dp[i+1][j+1] = 1+dp[i][j]
                else:
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])
        return dp[N][M]

    def longestPalindromeSubseq(self, s: str) -> int:
        return self.longestCommonSubseq(s, s[::-1])

 

2) DP로 푸는 법

 

아래 코드는 타임 초과...

 

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        # DP로 푸는 방법, 브루스포스, 디시즌트리, 메모이제이션

        cache = {}

        def dfs(l, r):
            if l < 0 or r == len(s): # left, right 인덱스가 s의 범위를 벗어나면
                return 0

            if (l, r) in cache:
                return cache[(l, r)]

            if s[l] == s[r]: # charactor match
                # 글자는 같지만, 
                # l==r 인덱스 위치가 같으면, 같은 문자이므로 1개로,
                # l!=r 인덱스 위치가 다르면, 다른 문자이므로 2개로.
                length = 1 if l == r else 2 
                cache[(l, r)] = length + dfs(l-1, r+1) # 이제, 둘다 인덱스 늘리고, 검색
            else: # don't match
                cache[(l, r)] = max(dfs(l-1, r), dfs(l, r+1))

            return cache[(l, r)]

        for i in range(lens(s)):
            dfs(i, i) # odd length, 홀수 길이
            dfs(i, i+1) # even length, 짝수 길이

        return max(cache.values())

 

최종 코드

 

 

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

        # 초기값: 부분 문자열 길이 1인 경우
        for i in range(n):
            dp[i][i] = 1

        # DP 테이블 채우기 (길이 2 이상 부분 문자열)
        for length in range(2, n + 1):  # 부분 문자열 길이
            for i in range(n - length + 1):  # 시작 인덱스
                j = i + length - 1  # 끝 인덱스
                if s[i] == s[j]:  # 양 끝 문자가 같으면
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:  # 다르면
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

        #return dp[0][n - 1]  # 전체 문자열의 최장 회문 부분 수열 길이 반환
        return dp[0][-1]  # 전체 문자열의 최장 회문 부분 수열 길이 반환