LeetCode[516] Longest Palindromic Subsequence

 516. Longest Palindromic Subsequence

Medium

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

 

Constraints:

• 1 <= s.length <= 1000
• s consists only of lowercase English letters.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { int[][] dp; public int longestPalindromeSubseq(String s) { int n = s.length(); dp = new int[n][n]; for(int i=n-1; i>=0; --i){ for(int j=i; j<n; ++j){ if(i==j) dp[i][j] = 1; else{ if(s.charAt(i)==s.charAt(j)){ dp[i][j] = dp[i+1][j-1]+2; }else{ dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]); } } } } return dp[0][n-1]; } }