5 lines Top-down DP and 5 lines Bottom-up DP Solution in Java


  • 0
    J

    5 lines Top-down DP Solution

    public class Solution {
        public int longestPalindromeSubseq(String s) {
            int[][] dp = new int[s.length()][s.length()];
            return longestPalindromeSubseq(s, 0, s.length() - 1, dp);
        }
        
        private int longestPalindromeSubseq(String s, int left, int right, int[][] dp) {
            if(left > right) return 0;
            if(dp[left][right] != 0) return dp[left][right];
            dp[left][right] = (s.charAt(left) == s.charAt(right)) ? (left == right ? 1 : 2) + longestPalindromeSubseq(s, left + 1, right - 1, dp): 
            	Math.max(longestPalindromeSubseq(s, left + 1, right, dp), longestPalindromeSubseq(s, left, right - 1, dp));
            return dp[left][right];
        }
    }
    

    5 lines Bottom-up DP Solution

    public class Solution {
        public int longestPalindromeSubseq(String s) {
            int[][] dp = new int[s.length()][s.length()];
            for(int gap = 0; gap < s.length(); gap++)
                for(int i = 0; i+gap < s.length(); i++)
                    dp[i][i+gap] = (s.charAt(i) == s.charAt(i+gap)) ? (gap == 0 ? 1 : 2 + dp[i+1][i+gap-1]) : Math.max(dp[i+1][i+gap], dp[i][i+gap-1]);
            return dp[0][s.length()-1];
        }
    }
    

Log in to reply
 

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