'('
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