Super easy to understand C++ solution with stack


  • 0
    Q

    The length of current 'run' is the current position minus the previous unresolved ')' .
    For example, ) () () , the length is 4 - 0. if we come to ) ()()() ))))) ()() , then again we do curPos - previous ')'. We use a stack store the characters, match and eliminate '( '. The unmatched ')' is available through st.top().

    Before we go through the s string, we first put a dummy ')' with position -1 into the stack.

    ) () so this case we will get run length 1-(-1 ) = 2.
    -1

    class Solution {
    public:
        int longestValidParentheses(string s) {
           std::stack< pair<char, int> > st;
           int max = 0;
           st.push( make_pair(')', -1) );             //put a un-matchable ) in the stack
           for(int i =0; i < s.size(); i++) 
           {
              if (s[i] == '(') {
                 st.push( make_pair('(', i));
              } else if(s[i] == ')')
              {
                 if(st.top().first == '(' )   //if top is ( then match and cancel
                 {
                    st.pop();          //match and cancel the previous  ( 
                    max = std::max( max, i - st.top().second);          get the length of current run and compare with max
                 } else 
                 {
                    st.push( make_pair(')', i));           //push
                 }
    
              }
    
           }
           return max;
        }
    };

Log in to reply
 

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