Clean recursion. C++. Suggest optimizations, anyone?


  • 0
    P
    class Solution {
    public:
        int longestPalindromeSubseq(string s) {
            vector<vector<int>> dp(s.size(), vector<int>(s.size(), -1));
            return ll(s, 0, s.size() - 1, dp);
        }
        int ll(const string& s, int l, int r, vector<vector<int>>& dp){
            if(l == r) return 1;
            if(l > r) return 0;
            if(dp[l][r] != -1) return dp[l][r];
            
            return dp[l][r] = (s[l] == s[r] ? 2 + ll(s, l + 1, r - 1, dp) : max (ll(s, l + 1, r, dp), ll(s, l, r - 1, dp)));
        }
    };

Log in to reply
 

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