Short C++ solution beats 99%


  • 0
    A

    The idea is using a vector as the dynamic programming table and modify the vector s.size() times, instead of making a full matrix

    class Solution {
    public:
        int longestPalindromeSubseq(string s) {
            if(s == "") return 0;
            
            vector<int> dp(s.size(), 1);
            int btwn, tmp;
            for(int i = 1; i < s.size(); i++){
                btwn = 0;
                for(int j = i - 1; j >= 0; j--){
                    tmp = dp[j];
                    if(s[i] == s[j]) dp[j] = btwn + 2;
                    else dp[j] = max(dp[j], dp[j + 1]);
                    btwn = tmp;
                }
            }
            return dp[0];
        }
    };
    

  • 0
    T

    great solution!!


Log in to reply
 

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