[LeetCode] 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".

Thought process:

1. Sub-problem: f( i, j ) = the LPS's length in the substring s( i, j )
2. Function: 
1. If s[ i ] == s[ j ], f( i, j ) = f( i + 1, j - 1 ) + 2.
2. Else, f( i, j ) = max( f( i + 1, j ), f( i, j - 1 ) ).
3. Initialization: if i == j, the string has only one character. Its LPS's length is 1.
4. Result: f( 0, length of s ).

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

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

Time complexity:
O(n^2)