Java Solution DP with explaination


  • 0
    C
    public int longestPalindromeSubseq(String s) {
            int len =  s.length();
            int[][] dp = new int[len][len];
            
            // bottom up approach
            for(int i=0; i<len; i++){
                for(int j=0; j+i<len; j++){
                    int k = j + i;
                    
                    // all single characters are palindrom
                    if(k == j){
                        dp[j][k] = 1;
                    }
                    // if first and last are same then 2 + mid
                    else if(s.charAt(j) == s.charAt(k)){
                        dp[j][k] = 2 + dp[j+1][k-1];
                    }
                    // if they are diff then max of substring without first and substring without last
                    else{
                        dp[j][k] = Math.max(dp[j+1][k], dp[j][k-1]);
                    }
                }
            }
            
            return dp[0][len - 1];
        }
    

Log in to reply
 

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