Simple Java DP Solution


  • 0
    R
    public class Solution {
        public int longestPalindromeSubseq(String source) {
            int n = source.length();
            int[][] LP = new int[n][n];
    
        //All sub strings with single character will be a palindrome of size 1
        for (int i=0; i < n; i++) {
            LP[i][i] = 1;
        }
        //Here gap represents gap between i and j.
        for (int gap = 1; gap < n; gap++) {   
            for (int i = 0; i< n-gap; i++ ) {
                        int j = i + gap; 
                        if(source.charAt(i) == source.charAt(j) && gap == 1) {
                            LP[i][j] = 2;
                        } else if(source.charAt(i) == source.charAt(j)) {
                            LP[i][j] = LP[i+1][j-1] + 2;
                        } else {
                            LP[i][j] = Math.max(LP[i][j-1], LP[i+1][j]);   
                        }
             }      
        }       
        return LP[0][n-1];      
    
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.