032.Longest Valid Parentheses

题目链接

题目

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:
1
2
3
Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

分析

  • 本题是一道Hard题目,其基于Valid Parentheses这个概念。
  • 有效序列的意思是 所有所有括号都可以相互匹配,符合数学定义。比如:()()(())(()())等均符合有效序列的定义。
  • 题目给定序列,序列内可能包含多个有效序列,返回最长序列的长度即可。
  • 本题目可以扩展为:序列是否为有效问题,具体做法为:如果 返回长度==序列长度,则整个序列为有效序列。

栈实现

  • 使用栈这里需要注意题目的要求,我们寻找的是最长的有效括号的长度,所以这是一个寻找连续子子串的问题。
  • 所以,为了判断连续的问题,我们在栈中保存每个符号的索引位置i,而不是每个符号的值。
  • 通过判断当前匹配右括号和栈弹出元素后的栈顶元素的索引位置,来记录最大匹配长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def longestValidParentheses(self, s: str) -> int:
if len(s) == 0:
return 0
res = 0
stack = [-1]
for i in range(len(s)):
if s[i] == "(":
stack.append(i)
else:
# 里边只有"("
stack.pop()
if len(stack):
# 上一个多余括号,或者从头开始算
res = max(res, i - stack[-1])
else:
# 如果stack是空,且输入')'
stack.append(i)
return res

动态规划

  • dp[i]表示以当前位置为终点的最长长度,则只能在)处更新;
  • 如果s[i-1-dp[i-1]]==’(‘,则说明当前位置可以和i-1-dp[i-1]位置匹配,dp[i]=dp[i-1]+2;
  • 然后还要加上匹配位置之前的最长长度dp[i]+=dp[i-dp[i]];
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def longestValidParentheses(self, s: str) -> int:
res = 0
s = ')' + s
dp = [0 for _ in s]
for i in range(1, len(s)):
if s[i] == ')':
if s[i - 1 - dp[i-1]] == '(':
dp[i] = dp[i-1] + 2
# 比如(()())
dp[i] += dp[i-dp[i]]
res = max(res, dp[i])
return res

032.Longest Valid Parentheses

https://iii.run/archives/a579b06121d2.html

作者

mmmwhy

发布于

2019-04-22

更新于

2021-05-30

许可协议