我的博客

leetcode 力扣 32 最长有效括号 python

目录
  1. 解答
    1. DP
    2. 两次遍历

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

示例 1:

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

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def longestValidParentheses(self, s: str) -> int:
dp = [0] * len(s)
ans = 0
for i in range(1, len(s)):
if s[i] == ')':
if s[i-1] == '(':
dp[i] = (dp[i-2] if i - 2 > 0 else 0) + 2
ans = max(ans, dp[i])
else:
j = i - dp[i-1] - 1

if j >= 0 and s[j] == '(':
dp[i] = dp[i-1] + 2
if j - 1 >= 0: dp[i] += dp[j - 1]
ans = max(ans, dp[i])
return ans

两次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def longestValidParentheses(self, s: str) -> int:
def fun(s, t):
left = 0
right = 0
max_length = 0
for ch in s:
if ch == t: left += 1
else: right += 1
if left == right: max_length = max(max_length, left<<1)
elif right > left:
left = 0
right = 0
return max_length
return max(fun(s, '('), fun(s[::-1], ')'))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def longestValidParentheses(self, s: str) -> int:
l = [-1]
max_length = 0
cur = 0
for i, ch in enumerate(s):
if ch == '(':
l.append(i)
else:
l.pop()
if not l:
l.append(i)
else:
max_length = max(max_length, i - l[-1])
return max_length

评论无需登录,可以匿名,欢迎评论!