问题
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.
解决思路和代码
这种括号配对问题，用堆栈法最好了。动态规划也行，麻烦一点。最开始用递归，不好做扩展匹配。代码用python实现的：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def duang(s):
if len(s) < 2:
return 0
str_stack = []
idx_stack = []
for i,c in enumerate(s):
if i > 0 and len(str_stack) > 0:
if c == ')' and str_stack[-1] == '(':
str_stack.pop()
idx_stack.pop()
continue
str_stack.append(c)
idx_stack.append(i)
if len(idx_stack) == 0:
return len(s)
idx_stack.append(len(s))
max_len = 0
for i,idx in enumerate(idx_stack):
if i == 0:
max_len = idx_stack[i]
continue
max_len = max(max_len, idx - idx_stack[i-1] - 1)
return max_len
class Solution(object):
def longestValidParentheses(self, s):
return duang(s)