A Different C++ Solution


  • 0
    J
    class Solution {
    public:
        int longestValidParentheses(string s) {
            int s_len = s.length();
            int max_len = 0;
            int valid_len = 0;
            stack<char> cstack;
            stack<int> istack;
            cstack.push('1');		// '1' as guard to mark the end of stack
            istack.push(0);		// set the first result as 0
            for(int i = 0; i < s_len; i ++){
            	if(s[i] == '('){
            		cstack.push(s[i]);
            		cstack.push('0');
            		istack.push(0);		//set the present result as 0
            	}
            	else{
            		if(cstack.top() == '0'){
            			cstack.pop();	//pop out '0'
            			cstack.pop();	//pop out '1'
            			valid_len = istack.top();   // istack.top() is the present result
            			istack.pop();	// pop out the  present result
            			valid_len += 2;	// because we found a new pair, we add 2 to the present result
            			int tmp_len = istack.top();   // tmp_len is the former result
            			istack.pop();    // pop the former result out
            			valid_len += tmp_len;	// add the former result to present result
            			istack.push(valid_len);
            		}
            		else{
            			if(istack.top() != 0)
            				istack.push(0);		//we make the present result as 0, continuous '(' as one 0
            		}
            	}
            }
    
            // find the max length from looking through istack
            while(!istack.empty()){
            	int top_len = istack.top();
            	istack.pop();
            	max_len = max_len > top_len ? max_len : top_len;
            }
            return max_len;
        }
    };
    

Log in to reply
 

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