Given a string containing just the characters '(' 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 1: This solution is more natural and easy to understand.
?
复制代码
class Solution:
? ? # @param s, a string
? ? # @return an integer
? ? def longestValidParentheses(self, s): ? ? ? ?
? ? ? ? stack = [(-1, ')')]
? ? ? ? maxLen = 0
? ? ? ? for i in range(len(s)):
? ? ? ? ? ? if s[i] == ')' and stack[-1][1] == '('
? ? ? ? ? ? ? ? stack.pop()
? ? ? ? ? ? ? ? maxLen = max(maxLen, i - stack[-1][0])
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? stack.append( (i, s[i]) )
? ? ? ? return maxLen
复制代码
?
?
?
?
Solution 2: It is smart but not practical
?
?
?
复制代码
class Solution:
? ? # @param s, a string
? ? # @return an integer
? ? def longestValidParentheses(self, s):
? ? ? ? #解题思路：返回括号串中合法括号串的长度。使用栈。这个解法比较巧妙，开辟一个栈，压栈的不是括号，而是未匹配左括号的索引！
? ? ? ? maxLen = 0
? ? ? ? stack = []
? ? ? ? last = -1
? ? ? ? for i in range(len(s)):
? ? ? ? ? ? if s[i] == '(':
? ? ? ? ? ? ? ? stack.append(i)
? ? ? ? ? ? else:
? ? ? ? ? ? ? ? if stack == []:
? ? ? ? ? ? ? ? ? ? last = i
? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? stack.pop()
? ? ? ? ? ? ? ? ? ? if stack == []:
? ? ? ? ? ? ? ? ? ? ? ? maxLen = max(maxLen, i - last)
? ? ? ? ? ? ? ? ? ? else:
? ? ? ? ? ? ? ? ? ? ? ? maxLen = max(maxLen, i - stack[-1])
? ? ? ? return maxLen