Easy Java Solution using DP


  • 0
    U

    Description -

    int lps(String s, int i, int j) - returns Longest Palindromic Subsequence in string s from between index i and j (both inclusive)

    Rest of the code is self explanatory.

    class Solution {
        private static int[][] dp;
    
        public int longestPalindromeSubseq(String s) {
            dp = new int[s.length()][s.length()];
            return lps(s, 0, s.length()-1);
        }
        
        private static int lps(String s, int i, int j) {
            if (i > j)
                return 0;
            if (dp[i][j] != 0)
                return dp[i][j];
            if (i == j) {
                dp[i][j] = 1;
            } else {
                if (s.charAt(i) == s.charAt(j))
                    dp[i][j] = Math.max(Math.max(2 + lps(s, i + 1, j - 1), lps(s, i + 1, j)), lps(s, i, j - 1));
                else
                    dp[i][j] = Math.max(lps(s, i + 1, j), lps(s, i, j - 1));
                
            }
            return dp[i][j];
        }
    }
    

Log in to reply
 

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