My solution with two stacks, want to share it.


  • 1
    F
    class Solution {
    public:
        int longestValidParentheses(string s) {
            /* idea: use two stack
            * stack 'left' stores '(' which are not macthed
            * stack 'right' stores the index of each macthed ')' as well as the number of pathrenthess it could match
            */
            if(s.length() < 2)
                return 0;
        
            stack<int> left;
            stack<pair<int, int> > right;
            for(unsigned int i = 0; i < s.length(); ++i){
                if (s[i] == '('){
                    left.push(i);
                }else{
                    if(!left.empty()){ 
                        int top = left.top();
                        left.pop();
                        while(!right.empty() && right.top().first > top)
                            right.pop();
                        int matchLen = i - top + 1;
                        if(!right.empty() && right.top().first + 1 == top){
                            matchLen += right.top().second;
                            right.pop();
                            right.push(make_pair(i, matchLen));
                        }else{
                            right.push(make_pair(i, matchLen));
                        }
                    }
                }
            }
            int maxLen = 0;
            while(!right.empty()){
                maxLen = max(maxLen, right.top().second);
                right.pop();
            }
            return maxLen;        
        }
    };

Log in to reply
 

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