Easy understanding


  • 0
    H
    public class Solution {
        public int LongestValidParentheses(string s) {
            if(s == null)   return 0; 
            Stack<int> lastMax = new Stack<int>();
            int max = 0, left = 0, len;
            for(int i = 0; i < s.Length; i++)
            {
                if((s[i] != '(' && s[i] != ')') || (s[i] == ')' && left == 0))  //invalid, left means whether there is 
                                                                                //'(' in the stack
                {
                    left = 0;
                    lastMax.Clear();
                }
                else if(s[i] == '(')            //push '(' as 0
                {
                    left++;
                    lastMax.Push(0);
                }
                else        //go combining
                {
                    len = 0;
                    if(lastMax.Count > 0)
                    {
                        if(lastMax.Peek() > 0)  len += lastMax.Pop();       //top is length
                        left--;                                             //top is '('
                        len += 2;
                        lastMax.Pop();
                        if(lastMax.Count > 0 && lastMax.Peek() > 0) len += lastMax.Pop();   //after combining, there
                                                                                       // is still a length on the top
                    }
                    if(len > max)   max = len;
                    lastMax.Push(len);      //push the length of valid Parentheses
                }
            }
            return max;
        }
    }

Log in to reply
 

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