Fork me on GitHub

Longest Palindromic Subsequence

Posted on

Description

https://leetcode.com/problems/longest-palindromic-subsequence/description/

Solution

The code is quite straightforward. The recursive formule is the following:

The string range from i to j can be reduced to the smaller case by two situations:

If the char at i and j is equal, then the largest prlindromic subseq is [i+1, j-1] + 2

Else, the largest prlindromic subseq is the larger value of [i+1, j], [i, j+1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int longestPalindromeSubseq(String s) {
        int lens = s.length();
        if (lens == 0) return lens;
        int[][] matrix = new int[lens][lens];
        for (int i = 0; i < lens; i++) matrix[i][i] = 1;
        for (int i = 0; i < lens - 1; i++)
            matrix[i][i + 1] = s.charAt(i) == s.charAt(i + 1) ? 2 : 1;
        
        for(int len = 3; len <= lens; len++)
            for (int start = 0; start <= lens - len; start++) {
                int end = start + len - 1;
                if (s.charAt(start) == s.charAt(end)) 
                    matrix[start][end] = matrix[start + 1][end - 1] + 2;
                else 
                    matrix[start][end] = Math.max(matrix[start][end - 1], matrix[start + 1][end]); 
        
            }
        return matrix[0][lens-1];
    }
}