with o(n) space


  • 0
    D
    int longestPalindromeSubseq(string s) {
        if(s.length() == 0)
             return 0;
            
        vector<vector<int> > nums(3, vector<int>(s.length(), 0));
        for(int i = 0;i < s.length();i ++)
            nums[0][i] = 1;
        
        for(int i = 1;i < s.length();i ++)
            for(int j = 0;j + i < s.length();j ++) {
                nums[i%3][j] = max(nums[(i+2)%3][j], nums[(i+2)%3][j+1]);
                if(s[j] == s[j+i])
                    nums[i%3][j] = max(nums[i%3][j], 2 + nums[(i+1)%3][j+1]);
            }
            
        return nums[(s.length()-1)%3][0];
    }

Log in to reply
 

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