Leetcode 32


  Posted on 07 Mar 2017
parentheses


Tutorial


Use a stack for the sequence. If it is a “(“ push its index in. If it is a “)”, check if the top element is a “(“. If so pop it. Otherwise, push the “)” index in. After we walked through the whole sequence. The stack is a list of the indices of the illegal characters. We just go through it to find the longest gap between two neighbours.

Solution


class Solution(object):
    def longestValidParentheses(self, s):
	"""
	:type s: str
	:rtype: int
	"""
	stk = []
	for i, ch in enumerate(s):
	    if ch == '(':
	        stk.append(i)
	    elif stk and s[stk[-1]] == '(':
	        stk.pop()
	    else:
	        stk.append(i)
	stk.append(len(s))
	stk = [-1] + stk
	ret = 0
	for i in range(len(stk) - 1):
	    ret = max(ret, stk[i + 1] - stk[i] - 1)
	return ret