Leetcode 516. Longest Palindromic Subsequence (Python)

Related Topic

Dynamic-Programming.

Description

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

Sample I/O

Example 1

Input: "bbbab"
Output: 4
One possible longest palindromic subsequence is "bbbb".

Example 2

Input: "cbbd"
Output: 2
One possible longest palindromic subsequence is "bb".

Methodology

This question can be solved by Dynamic Programming. However there are various way to implement DP. It is similar with question 647. Palindromic Substrings.

Here is subsequence not substring

To find if the subsequence is palindromic, we need to set each element’s index as it’s start index then go through all element’s after the start index to find all the number of palindromic subsequence for the current element. If the current subsequence include the previous subsequence, then add 2 to the number of previous subsequence(1 for start and 1 for end). Otherwist, we need to get the maximum number from start element and end element.

Find the base case:

1. If there is 1 character, then the length of palindromic subsequence is 1.
2. If there are 2 character:
   1. First element and last element are same, then length of palindromic subsequence is 2.
   2. First element and last element are different, then length of palindromic subsequence is 1

Find the pattern:

We will check if each palindromic subsequence contain other palindromic subsequence. If the current palindromic subsequence contain other palindromic subsequence then current number is contained palindromic subsequence + 2. If the current palindromic subsequence contain does not contain other palindromic subsequence then current number is 2. If the current subsequence is not palindromic, then we need find the max number of it’s contained palindromic subsequence.

Answer:

Return the dp[0][n-1] as we start from last character of the string

Code

def longestPalindromeSubseq(self, s: str) -> int:
        if not s: return 0
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        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] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        return dp[0][n - 1]

BigO

Create dp list will cost O(n^2) and iterate the dp will cost (n^2/2) in total will be O(n^2*2/3)