easy to understand, short clean C++ code: transform the problem to longest common subsequence


  • 0
    S

    This problem can be transformed to another simple dp problem: find the longest commom subsequence between s and rs(reversal of s).

    int longestPalindromeSubseq(string s) 
    {
        string rs = s;
        reverse(rs.begin(), rs.end());
         
        //find the longest commom subsequence for s and rs  
        vector<vector<int> > dp(s.size()+1, vector<int>(s.size()+1, 0));
            
        for(int i = 1; i <= s.size(); ++i)
        for(int j = 1; j <= s.size(); ++j)
        {
            if(s[i-1] == rs[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
            
        return dp[s.size()][s.size()];
    }
    

Log in to reply
 

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