给你一个只包含 '(' 和 ')' 的字符串,找出最长有效(格式正确且连续)括号子串的长度
分析
- 第一想法想到的是栈,但是也有一些陷阱要注意
- 就是需要弹出后再考虑长度更新,另外需要考虑到栈为空的时候
- 方案二是动态规划,但是比较难想,就是当前为“)"去寻找最大长度,分成两部分,一部分是上一个也是(, 另一个上一个是")",但是也有可能之前更远还有能匹配的括号
- 方案三是技巧,要非常熟悉括号的规律,以从左到右为例,如果要最大长度,那么最大的长度就是有效右扩号的两倍,另外也需要考虑从右到左再做一次
方案一
class Solution:
def longestValidParentheses(self, s: str) -> int:
# 往前遍历,如果碰到")",就判断栈的最后一位是不是"(", 如果是"(", 则消除并判断,如果是")", 则压入
n = len(s)
max_len = 0
# 初始化第一位,因为这个涉及到有可能有"()"这样的,弹出后,下一个就是空的,或者下面特别处理也行
#stack = [(")", -1)]
stack = []
for i in range(n):
if s[i] == "(":
stack.append((s[i],i))
else:
if stack and stack[-1][0] == "(":
# pop需要放到第一位,因为需要找到弹出后的后面那一位才是最远的索引
stack.pop()
if not stack:
max_len = max(max_len, i + 1)
else:
max_len = max(max_len, i - stack[-1][-1])
else:
stack.append((s[i],i))
return max_len
方案二
class Solution:
def longestValidParentheses(self, s: str) -> int:
# 动态规划,这个有点难想,当时也可以熟悉动态规划的过程
n = len(s)
# 这个定义是以i为结束的括号子串的最大长度
dp = [0]*n
max_res = 0
for i in range(1, n):
if s[i] == ")":
if s[i - 1] == "(":
dp[i] = 2 + (dp[i - 2] if i > 2 else 0)
elif i - dp[i - 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 0 )
max_res = max(max_res, dp[i])
# 有时候是用最大,有时候才是最后
return max_res
方案三
class Solution:
def longestValidParentheses(self, s: str) -> int:
# 还有一个就感觉有点技巧了,是比较了解括号的规律,
# 最大长度窗口肯定是在右括号等于左括号时出现
# 有个问题就是如果只是从左到右,有可能右括号永远不会可以左括号一样,所以可以反过来再做一次
left, right, n = 0, 0, len(s)
max_res = 0
for i in range(n):
if s[i] == "(":
left += 1
else:
right += 1
if left == right :
max_res = max(max_res, right * 2)
elif right > left:
left, right = 0, 0
# 陷阱1,需要重新初始化left和right
left, right = 0, 0
for i in range(n - 1, -1, -1):
if s[i] == ")":
right += 1
else:
left += 1
if left == right:
max_res = max(max_res, left * 2)
elif left > right:
right, left = 0, 0
return max_res