Java DP solution


  • 0
    K

    Find the number of minimum characters required to be deleted to make the string palindrome and then subtract that number from the length of given string.

    public class Solution {
    public int longestPalindromeSubseq(String s) {
    if(s==null)
    return 0;
    int l=s.length();
    int [][] dp =new int[l][l];
    for(int i=1;i<=l;i++){
    for(int j=0;j<l-i+1;j++){
    int end=j+i-1;
    if(j==end){
    dp[j][end]=0;
    }
    else{
    if(s.charAt(j)==s.charAt(end))
    dp[j][end]=dp[j+1][end-1];
    else
    dp[j][end]=Math.min(dp[j][end-1],dp[j+1][end])+1;
    }
    }
    }
    return l-dp[0][l-1];

    }
    

    }


Log in to reply
 

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