Leetcode 516. Longest palindromic subsequence

stuff about computer science and programming
Post Reply
User avatar
dendiz
Site Admin
Posts: 234
Joined: Wed Oct 10, 2018 3:48 am

Leetcode 516. Longest palindromic subsequence

Post by dendiz » Thu Jan 24, 2019 2:41 pm

Given a string s, find the longest palindromic subsequences length in s. You may assume that the maximum length of s is 1000.
I despise these types of questions. Who likes dynamic programming anyways?

So the approach is the following:

Observation 1.

each 1 character subsequence is a palindrome.

Track the longest palindrome in substring(i, j) (i < j) as an entry in a 2D array with (i,j).
Due to observation 1. all items in the diagonal [i == j] will be 1. Get that out of the way

Code: Select all

        int[][] dp = new int[s.length()][s.length()];
        for(int i=0;i<s.length();i++) {
            dp[i][i] = 1;
        }
If the example input is "bbbab" scan the input with a sliding window that increases by 1 when it reaches the end, e.g

1. [bb]bab, b[bb]ab, bb[ba]b, bbb[ab]
2. [bbb]ab, b[bba]b, bb[bab]
3. [bbba]b, b[bbab]
4. [bbbab]

at each iteration notice that the previous iteration will contain the longest palindromic subsequence seen before it.

E.g iteration 2, step 2 b[bba]b:
bba is not a palindrome so the longest palindrome yet is the max of (bb, ba). ba is not a palindrome but bb is so the length is 2.

at each iteration if the char(i) == char(j) then the length of the palindrome will increase by 2 and will be 2 + the length of the previous palindrome.

So the dynamic programming relation is:

Code: Select all

DP[i][j] = 1 if i == j
DP[i][j] = 2 + DP[i+1][j-1] if char[i] == char[j]
DP[i][j] = max(DP[i+1][j], DP[i][j-1])
2019-01-24 06_39_09-Bamboo Paper.png

Code: Select all

    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length()];
        for(int i=0;i<s.length();i++) {
            dp[i][i] = 1;
        }
                
        for(int d=1;d<s.length();d++) {
            for(int j=d;j<s.length();j++) {
                int i = j - d;
                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][s.length() - 1];
    }
traversing the array in this weird sliding window manner is a bit confusing. The outer loop defines the length of the current sliding window from
1 to len(input). j defines the end of the window, and i defines the start of the window.

Post Reply