Based on DP Longest Common Subsequence


  • 0
    G
    public int longestPalindromeSubseq(String s) {
    	
    	if(s == null || s.equals("")) return 0;
    	
    	String t = new StringBuilder(s).reverse().toString();
    	
    	int[][] dp = new int[s.length()+1][t.length()+1];
    	
    	for(int i = 1; i <= s.length(); i++){
    		for(int j = 1; j <= t.length(); j++){
    			dp[i][j] = s.charAt(i-1) == t.charAt(j-1) ? dp[i-1][j-1]+1 : Math.max(dp[i][j-1], dp[i-1][j]);
    		}
    	}
    	
    	return dp[s.length()][t.length()];
    }
    

    What we're looking for is the longest common subsequence between a string and its reverse, that's what a palindromic subsequence is. Got this idea based on the Delete Operation for Two Strings problem. Time and Space O(n^2), runs in 79 ms, not the most impressive runtime, but I think it's a bit easier to understand than trying to combine the DP subsequence problem with the DP longest palindrome substring problem.


Log in to reply
 

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