[LeetCode]32. 最长有效括号(Longest Valid Parentheses)

题目描述

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。

示例 1:

输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”

示例 2:

输入: “)()())”
输出: 4
解释: 最长有效括号子串为 “()()”

解题思路

  1. 解法一:栈。遇到左括号时入栈,遇到右括号时出栈判断是否为左括号,匹配则将这两个坐标记录下来,否则清空栈。最终将所有的左右坐标统一排序,找出最长的连续升序数列即为结果(可通过举例验证!)!
  2. 解法二:动态规划。转移方程为:
  3. 解法三:双指针。首先从左到右扫描字符串,出现 ( 时,增加 left 计数器,出现 ) 时,增加 right 计数器,每当两个计数器相等时,说明刚好找到了匹配的括号,计算长度并更新最大值,若 right 大于 left 时,将两个计数器归零。接着从右到左扫描字符串,取最大值。一个例子可见双向扫描的作用:()((())

代码

Python 3.6

解法一:栈

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
class Solution:
def longestValidParentheses(self, s: str) -> int:
if not s:
return 0
stack = []
res = []
for i in range(len(s)):
if s[i] == ")":
if len(stack) > 0 and s[stack[-1]] == "(":
res.append(stack.pop())
res.append(i)
else:
stack = []
else:
stack.append(i)
res.sort()
max_len = 0
tmp_len = 1
for i in range(len(res)):
if (i < len(res) - 1) and (res[i + 1] - res[i] == 1):
tmp_len += 1
else:
max_len = max(tmp_len, max_len)
tmp_len = 1
return max_len

执行用时 : 80 ms
内存消耗 : 14.4 MB

解法二:动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def longestValidParentheses(self, s: str) -> int:
if not s:
return 0
length = len(s)
dp = [0] * length
for i in range(1, length):
if s[i] == "(":
continue
if s[i - 1] == "(":
dp[i] = dp[i - 2] + 2 if (i - 2 >= 0) else 2
elif i - dp[i - 1] - 1 >= 0 and s[i - dp[i - 1] - 1] == "(":
dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2] if (i - dp[i - 1] - 2 >= 0) else dp[i - 1] + 2
return max(dp)

执行用时 : 96 ms
内存消耗 : 14.1 MB

解法三:双指针

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
class Solution:
def longestValidParentheses(self, s: str) -> int:
if not s:
return 0
length = len(s)
left, right = 0, 0
i = 0
max_len = 0
while i < length:
# from left to right
if s[i] == "(":
left += 1
else:
right += 1
if left == right:
max_len = max(max_len, 2 * right)
elif left < right:
left, right = 0, 0
i += 1
i = length - 1
left, right = 0, 0
while i >= 0:
# from right to left
if s[i] == ")":
right += 1
else:
left += 1
if left == right:
max_len = max(max_len, 2 * left)
elif left > right:
left, right = 0, 0
i -= 1
return max_len

执行用时 : 72 ms
内存消耗 : 14 MB

参考

https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-powcai/
https://leetcode-cn.com/problems/longest-valid-parentheses/solution/zui-chang-you-xiao-gua-hao-by-leetcode