Two solutions, one is based on stack, the other is memorization.


  • 0

    The solution using stack is easy. Just try to keep the open (left) parentheses.

    class Solution {
    public:
    int longestValidParentheses(string s) {
        vector<int> stac;
        stac.push_back(-1);
        int size=s.length();
        int res=0;
        for(int i=0; i<size; ++i){
            if(s[i]=='('){
                stac.push_back(i);
            }
            else{
                stac.pop_back();
                if(!stac.empty()){
                    res=max(res, i-stac.back());
                }
                else{
                    stac.push_back(i);
                }
            }
        }
        return res;
    }};
    

    But, by intuition, this kind of problem could be solved by DP, or memorization. Because there are a lot of duplicated checking if without memorization. Whenever you meet a ')', you need to:

    1. look back one step to see if it's a '(',
    2. Or, if it's a ')', jump back based on the memorized index to find another '('.
    3. Add up previous valid parentheses.

    Then we could have the following 8ms solution.

    class Solution {
    public:
    int longestValidParentheses(string s) {
        int size=s.length();
        int res=0;
        vector<int> d(size, 0);
        for(int i=1; i<size; ++i){
            if(s[i]==')'){
                int prev=i-1-d[i-1];
                if(prev>=0 && s[prev]=='('){
                    d[i]=d[i-1]+2;
                    if(prev>1){
                        d[i]=d[i]+d[prev-1];
                    }
                    res=max(res, d[i]);
                }
            }
        }
        return res;
    }};

Log in to reply
 

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