Longest Valid Parentheses
Description
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
1
2
3
| Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
|
**Example 2:**
```
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"
```
输出最长的左右括号匹配的子串长度
Solution
逐个字符扫描并记录左右括号长度，当左右括号数量相等时，左右括号达到全匹配。
如果只从左往右扫描，"((()"这种左括号多于右括号的会被判断为0，所以需要进行一次从右往左扫描。
"())()()"这种中间多出右括号的情况，需要重置计数器，从后面继续扫描。
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| func longestValidParentheses(s string) int {
longest := 0
left, right := 0, 0
check_longest := func() {
// 如果左右相等则此时左右括号匹配
if left == right {
if left * 2 > longest {
longest = left * 2
}
}
}
// 从左往右扫描
for i := 0; i < len(s); i++ {
if s[i] == '(' {
left++
} else {
right++
// 右括号多于左括号，则不满足连续匹配规则，需要重置
if right > left {
left, right = 0, 0
continue
}
}
check_longest()
}
left, right = 0, 0
// 从右往左扫描
for i := len(s) - 1; i >= 0; i-- {
if s[i] == '(' {
left++
// 左括号多于右括号，则不满足连续匹配规则
if left > right {
left, right = 0, 0
continue
}
} else {
right++
}
check_longest()
}
return longest
}
|
Similar Problem
20. Valid-Parentheses