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

  • 0

    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;
                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.