[leetcode] Longest Valid Parentheses @python
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
