[516. Longest Palindromic Subsequence] #leetcode

516_0905.java

class Solution {
  // O(2^n) O(n)
    public int longestPalindromeSubseq(String s) {
        return helper(0, s.length()-1, s);    
    }
    
    private int helper(int left, int right, String s) {
        if (left == right) return 1;
        if (left > right) return 0;
        return s.charAt(left) == s.charAt(right) ? 2 + helper(left+1, right-1, s) :
            Math.max(helper(left+1, right, s), helper(left, right-1, s));
    }
    
}

class Solution2 {
  // O(n^2) O(n^2)
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] mem = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                mem[i][j] = -1;
            }
        }
        return helper(0, n-1, s, mem);    
    }
    
    private int helper(int left, int right, String s, int[][] mem) {
        if (left == right) return 1;
        if (left > right) return 0;
        if (mem[left][right] != -1) return mem[left][right];
        int count = s.charAt(left) == s.charAt(right) ? 2 + helper(left+1, right-1, s, mem) :
            Math.max(helper(left+1, right, s, mem), helper(left, right-1, s, mem));
        mem[left][right] = count;
        return count;
    }
    
}

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