Java Solution with DP


  • 0
    S
        public int longestPalindromeSubseq(String s) {
            int leng = s.length();
            int[][] dp = new int[leng][leng];
            for(int i =0; i<leng; i++){
                dp[i][i] = 1;
            }
            for(int i = 1; i<leng; i++){
                for(int j = 0;j<leng-i; j++){
                    if(s.charAt(j) == s.charAt(j+i)){
                        if(i==1){
                            dp[j][j+i] = 2;
                        }
                        else{
                            dp[j][j+i] = dp[j+1][j+i-1]+2;
                        }
                    }
                    else{
                        if(i==1){
                            dp[j][j+i] = 1;
                        }
                        else{
                            dp[j][j+i] = Math.max(dp[j][j+i-1], dp[j+1][j+i]);
                        }
                    }
                }
            }
            return dp[0][leng-1];
        }
    }

Log in to reply
 

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