516. Longest Palindromic Subsequence

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

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".

Solution

(1) Java

(2) Python

class Solution:
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        if s == s[::-1]:
            return len(s)
        dp = [[0 for _ in range(len(s))] for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1
        rst = 1
        for l in range(1, len(s)+1):
            for i in range(len(s)-l+1):
                j = i + l - 1
                if s[i] == s[j]: 
                    if j-i < 2:
                        dp[i][j] = j-i+1
                    else:
                        dp[i][j] = dp[i+1][j-1]+2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
                rst = max(rst, dp[i][j])
        return rst

(3) Scala