very easy to understand with detailed explain using dynamic programming just like longest common subsequence


  • 1
    5
    class Solution {
    public:
        int longestPalindromeSubseq(string s) {
            int size = s.size();
            if (size <= 1) {
                return size;
            }
            /*dp[i][j] means from index i to index j, the longest palindromic subsequence*/
            vector<vector<int> > dp(size + 1, vector<int> (size + 1, 0));
    
            /*dp initialization dp[i][i] means contains one character so it equals one*/
            for (int i = 1; i <= size; ++i) {
                dp[i][i] = 1;
            }
    
           /*j means move the right i means mean to left*/
            for (int j = 1; j < size; ++j) {
                for (int i = j - 1; i >= 0; --i) {
                    if (s[i] == s[j]) {
                       /*bab i = 0, j = 2  dp[0][2] = dp[1][1] + 2, and like lcs we should compare to 
                       dp[0][1] and d[1][2]  to get the longest*/
                        dp[i][j] = max(dp[i+1][j - 1] + 2, max(dp[i+1][j], dp[i][j-1]));
                   }
                    else {
                        dp[i][j] = max(dp[i+1][j-1],max(dp[i+1][j], dp[i][j-1]));
                    }
                }
            }
            return dp[0][size - 1];
        }
    };
    

  • 0
    Q

    Very impressive


  • 0
    C

    @540485909 Why my python version TLE?

    class Solution(object):
        def longestPalindromeSubseq(self, s):
            """
            :type s: str
            :rtype: int
            """
            N = len(s)
            dp = [[0 for _ in range(N)] for __ in range(N)]
            
            for i in range(N):
                dp[i][i] = 1
           
            for j in range(1, N):
                for i in range(j-1, -1, -1):
                    if s[i]==s[j]:
                        dp[i][j] = max([ dp[i+1][j-1]+2, dp[i+1][j], dp[i][j-1] ])
                    else:
                        dp[i][j] = max([ dp[i+1][j-1], dp[i+1][j], dp[i][j-1] ])
                        
            return dp[0][N-1]
    

  • 0
    5

    @Chengcheng.Pei thanks for your comment, I think this may be the reason the python is slow than c++, so you can't AC using an algorithm of O(n2), here is an example of python AC code python ac code


Log in to reply
 

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