8ms C++ simple DP solution


  • 4
    N
    class Solution {
    public:
        int longestValidParentheses(string s) {
            size_t numLefts = 0, maxLen = 0;
            vector<size_t> f(s.size(), 0);
            for(size_t i = 0;i < s.size();++i){
                if(s[i] == '(')
                    ++numLefts;
                else if(numLefts > 0){
                    --numLefts;
                    f[i] = f[i - 1] + 2;
                    int prev = i - f[i];
                    if(prev > 0)
                        f[i] += f[prev];
                    maxLen = max(maxLen, f[i]);
                }
            }
            return maxLen;
        }
    };

Log in to reply
 

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