'(' and ')', find the length of the longest valid (well-formed) parentheses substring.
For
"(()", the longest valid parentheses substring is "()", which has length = 2.
Another example is
")()())", where the longest valid parentheses substring is "()()", which has length = 4.
Solution:
class Solution:
# @param s, a string
# @return an integer
def longestValidParentheses(self, s):
stack = []
lastError = -1
longestValidParentheses = 0
for i in range(0, len(s)):
if s[i] =='(':
stack.append(i)
else:
if len(stack) == 0:
lastError = i;
else:
stack.pop()
if len(stack)==0:
validTill = lastError
else:
validTill = stack[-1]
longestValidParentheses = max(longestValidParentheses, i-validTill)
return longestValidParentheses
No comments :
Post a Comment