Java DP solution -- Longest Common Subsequence


  • 0
    G

    There are many good DP solutions to this problem, but I just introduce a different view to this problem. Hope it helps.

    The palindrome subsequence remains the same both from left to right and right to left. We can utilize this property and the problem changed to: reverse the string and find LCS with original string, which is an old and classic DP problem.

    class Solution {
        
        public int longestPalindromeSubseq(String s) {
            String t = new StringBuilder(s).reverse().toString();
            // longest common sequence
            int n = s.length();
            int[][] dp = new int[n + 1][n + 1];
            for (int i = 0; i < n; i ++) {
                for (int j = 0; j < n; j ++) {
                    if (s.charAt(i) == t.charAt(j)) {
                        dp[i + 1][j + 1] = dp[i][j] + 1;
                    } else {
                        dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                    }
                    
                }
            }
            return dp[n][n];
        }
    }
    

Log in to reply
 

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