An One-Pass Solution by Python


  • 1
    A
    class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            dic = {}
            dic[-1] = 0
            stack = []
            stack.append(-1)
            result = 0
            for i in xrange(0, len(s)):
                if s[i] == '(':
                    dic[i] = 0
                    stack.append(i)
                else:
                    if len(stack) < 2:
                        result = max(result, dic[stack[-1]])
                        dic[stack[-1]] = 0
                        continue
                    dic[stack[-2]] += i - stack[-1] + 1
                    result = max(result, dic[stack[-2]])
                    stack.pop()
            return result

  • 0
    J
    class Solution
    {
        //can you help me with my solution
    public:
    	int longestValidParentheses(string s){
    		stack <int> ss;
    		int len=s.size();
    		int result=0;
    		for (int i=0;i<len;i++){			
    			if (s[ss.top()]=='(' && !ss.empty() && s[i]==')' ){
    				ss.pop();
    				if (ss.empty()){
    					result=i+1;
    				}
    				else
    					result= max(i-ss.top(),result);
    			}
    			else{
    				ss.push(i);
    			}
    		}
    
    		return result;
    	}
    };

Log in to reply
 

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