Straight forward Java DP solution


  • 66

    dp[i][j]: the longest palindromic subsequence's length of substring(i, j)
    State transition:
    dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j)
    otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1])
    Initialization: dp[i][i] = 1

    public class Solution {
        public int longestPalindromeSubseq(String s) {
            int[][] dp = new int[s.length()][s.length()];
            
            for (int i = s.length() - 1; i >= 0; i--) {
                dp[i][i] = 1;
                for (int j = i+1; j < s.length(); 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][s.length()-1];
        }
    }
    

    Top bottom recursive method with memoization

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

  • 6
    C

    @tankztc Great Solution!
    Increasing distance between i and j may be better.

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

  • 0

    @ckcz123 why increasing distance is better?


  • 0
    D

    Nice write in cpp

    int longestPalindromeSubseq(string s) {
        vector<vector<int>> dp(s.size(), vector<int>(s.size(),0));
        int len = s.size();
        for(int i = 0; i < len; i++)
            dp[i][i] = 1;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i + 1 ; j < len ; j++) {
                if(s[i] == s[j]) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                } else {
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][len - 1];
    }

  • 0
    X
    This post is deleted!

  • 0
    W

    I don't get why same python solution got TLE.

    @administrators
    @1337c0d3r

    '''

    def longestPalindromeSubseq(self, s):
    
        n = len(s)
        dp = [[0 for j in xrange(n)] for i in xrange(n)]
    
        for i in xrange(n - 1, -1, -1):
            dp[i][i] = 1
            for j in xrange(i + 1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    
        return dp[0][n - 1]
    

    '''

    Another similar version I wrote initially before I saw the discussion

    '''

    def longestPalindromeSubseq(self, s):
        
        if not s:
            return 0
            
        n = len(s)
        dp = [[1 for j in xrange(n)] for i in xrange(n)]
        
        for i in xrange(1, len(s)):
            for j in xrange(i - 1, -1, -1):
                if s[i] == s[j]:
                    dp[j][i] = dp[j + 1][i - 1] + 2 if i - j > 1 else 2
                else:
                    dp[j][i] = max(dp[j][i - 1], dp[j + 1][i])
        
        #print dp 
        return dp[0][-1]
    

    '''


  • 0
    V

    I tested with test case "baba". Shouldnt it be giving a length of 4, if test case "abba" can give output 4. I am confused.


  • 0

    @vicmania2007
    "baba" should output 3, the longest palindromic subsequence is either "bab" or "aba"
    "abba" give a output 4, the longest palindromic subsequence is itself.


  • 0
    V

    @tankztc I got the mistake..I worked out the code, but i am not able to understand the logic behind using a 2d matrix and performing some form of count based on char i = j match. Can you explain it? Thanks.


  • 3

    @vicmania2007 ,
    dp[i][j] store the length of the longest palindromic subsequence of substring(i,j). So how can we get it?
    If s.charAt(i) == s.charAt(j), that means we can pick these two char and the longest palindromic subsequence in substring(i+1, j-1) to form a longer subsequence that is palindromic, right

    If s.charAt(i) != s.charAt(j), what's the possible result can be? It lives in the substring(i+1, j) and substring(i, j-1), we pick the bigger one from them.

    Hope this helps.


  • 0
    V

    @tankztc I now got the point..Thanks for making me understand...I would say, i am more a fan of the recursive solution..


  • 0
    S

    the DP solution is tricky as f, not straight forward at all though.

    You only go through the top-right part above the diagonal in the dp[][] matrix, leave the bottom-left part below diagonal 0 to handle the i>j cases which is brilliant.

    How did you come up with the dp approach? I mean, if I met this problem in an interview, probably I could figure it out with the recursive solution, but would definitely stuck with the dp way.


  • 1

    @SB.Hu I agreed with that. Recursive solution is more straight forward, I think it's totally okay to do it using top-down recursive way, after all recursive search with memorization is also DP. To do bottom-up iterative DP, I think the most important part is figuring out the state transition function.


  • 5

    Great solution, very concise. At first I see the 2-D array and think matrix (rows and columns) this confused me. But then I realized the 2-D array is actually left and right indexes in the string and that led me to see the solution clearly. If anyone else had trouble understanding this here is some more explanation and code.

    You will be considering substrings starting at left and ending at right (inclusive). To do this you will iterate over all lengths from 1 to n and within each length iterate over staring (or left) position. The key is that you get the answers for a single length at all start positions before going to the next length because the dp depends on the answers from shorter lengths. If you do it this way you will have 3 cases to consider on every iteration, pick the one with the highest value.

    • the answer from removing the left edge char
    • the answer from removing the right edge char
    • and if the left and right chars are equal, 2 plus the answer from removing both left and right

    the 3rd case is how the answer grows. After iterating through all you will have performed O(n^2) checks and used O(n^2) memory, the answer is where left is 0 and right is n-1 which will be your very last calculation.

    To show the 3 cases more clearly I break out lengths 1 and 2 because their logic is simplified.

        public int LongestPalindromeSubseq(string s) 
        {
            int n = s.Length;
            int[,] dp = new int[n,n];
            
            // len 1
            for (int i = 0; i < n; i++) dp[i,i] = 1;
            
            // len 2
            for (int i = 0, j = 1; j < n; i++, j++) dp[i,j] = s[i] == s[j] ? 2 : 1;
            
            // len 3 and up
            for (int len = 3; len <= n; len++)
            {
                for (int i = 0, j = len - 1; j < n; i++, j++)
                {
                    // better of without left or without right
                    int max = Math.Max(dp[i,j-1], dp[i+1,j]);
                    if (s[i] == s[j])
                    {
                        // now check 2 plus without left and without right
                        max = Math.Max(max, 2 + dp[i+1,j-1]);
                    }
                    dp[i,j] = max;
                }
            }
            
            return dp[0,n-1];
        }
    

  • 0
    	public int longestPalindromeSubseq(String s) {
    		int n = s.length();
    		char[] sc = s.toCharArray();
    		int[][] dp = new int[n][n];
    
    		for(int j = 0; j < n; j++){
    			dp[j][j] = 1;
    			for(int i = j - 1; i >= 0; i--){
    				if(sc[i] == sc[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];
    	}

  • 1
    C

    Why this one is wrong? How is the order decided? Thank you!

    int longestPalindromeSubseq(string s) {
    int n = s.size();
    
    vector<vector<int>> dp(n, vector<int>(n, 0));
    
    for (int i=0; i<n; i++){
        dp[i][i]=1;
    }
    
    for (int i=0; i<n; i++){
         for (int j=i+1; j<n; j++){
             if (s[i]==s[j])
                 dp[i][j] = dp[i+1][j-1]+2;
             else
                 dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
         }
     }
     
     return dp[0][n-1];
    }

  • 3

    @coder2 The order can be decided from the state transition. dp[i][j] is depend on dp[i+1][j-1], which means to calculate dp[i][j], you need to know the value of dp[i+1][j-1] first ("i" is relying on "i+1", "i+1" need to be calculate first, that's why the i loop reverse order)


  • 0
    C

    At first, I reverse the string to convert the problem to LCS Problem and I think this can be better to understand. However, my code still needs improvement. Thanks for your sharing. You expand my outlook!!!

        public int longestPalindromeSubseq(String s) {
            String newstr = reverse(s);
            int n = s.length();
            int [][]dp = new int[n + 1][n + 1];
            for (int i = 1; i < n + 1; i++){
                for (int j = 1; j < n + 1; j++){
                    if (s.charAt(i - 1) == newstr.charAt(j - 1)){
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    } else {
                        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                    }
                }
            }
            return dp[n][n];
        }
        private String reverse(String s){
            StringBuffer sb = new StringBuffer(s);
            sb.reverse();
            return sb.toString();
        }

  • 8

    I draw a table for better illustrating. The logic is same with @tankztc

    Example: input string s : axbdba
    step1: fill the table with start case, dp[i,i] == 1, sicne all single char in a string is a palindrome, which length is 1.
    0_1489775602324_1.PNG

    step 2:When s[i] != s[j] case
    0_1489775871740_2.PNG

    Step 3: When s[i] == s[j] case
    0_1489776224079_3.PNG

    Step 4: fill out all the table, the dp[s.Length,0] is what we are looking for. And as the arrow point, the subsequence is ##dba, which is abdba
    0_1489776418221_4.PNG
    C# code:

        public int LongestPalindromeSub (string s) {
            int[,] dp = new int[s.Length, s.Length];
            
            for(int i = 0; i< s.Length; i++)
            {
                dp[i,i] = 1;
                for(int j = i-1; j>=0; j--)
                {
                    if(s[i] == s[j])
                    {
                        dp[i,j] = 2 + dp[i-1,j+1];
                    }
                    else
                    {
                        dp[i,j] = Math.Max(dp[i-1,j], dp[i,j+1]);
                    }
                }
            }
            return dp[s.Length-1,0];
        }
    

  • 0
    M

    For the same testcase, I got 300ms(TLE) by using hashmap but 9ms by using array. Can anyone explain why using hashmap gets TLE but array doesn't? Thanks!


Log in to reply
 

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