32. 最长有效括号
题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/longest-valid-parentheses
题目
给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
示例 2:
输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
解题思路
思路:栈
题目中,要查找有效括号,有可能需要从内往外扩展,这符合栈先入后出的特性。
我们先使用暴力解,来尝试解决这个问题。
有效的括号是成对出现的,那么我们尝试罗列所有可能的非空偶数长度子字符串,判断其是否有效。
当我们遇到左括号 (
时,我们将它入栈。当遇到右括号 )
时,从栈中弹出一个左括号 (
,如果栈中没有了左括号,或者遍历完成后栈中还保留有元素,那么这个子字符串就是无效的。循环遍历,更新最大的长度。具体的代码如下:
def longestValidParentheses(self, s: str) -> int:
def is_valid(s):
stack = []
for i in range(len(s)):
if s[i] == '(':
stack.append('(')
elif stack and stack[-1] == '(':
stack.pop()
else:
return False
return not stack
max_len = 0
for i in range(len(s)):
for j in range(i+2, len(s)+1, 2):
if is_valid(s[i:j]):
max_len = max(max_len, j-i)
return max_len
但是这里最终的执行结果是超时。因为我们的方法是从字符串中罗列出所有可能的非空偶数子字符串,这里需要的时间复杂度为 O(n^2)
。
在这里,我们尝试进行优化。
上面的暴力解法,是要先罗列所有可能的子字符串。在这里,我们直接在遍历的过程中去判断所遍历的子字符串的有效性,同时维护最大的长度。
这里有个需要注意的地方,开始的时候,需要先将 -1
压入栈中(后面解释)。具体实现的方法如下:
- 当遇到
(
时,将其索引压入栈中; - 当遇到
)
时,弹出栈顶元素,计算有效长度,循环遍历,维护最大的长度。
第二步中,计算有效长度。这里直接用当前遍历的字符索引减去栈顶元素的索引。此时的栈顶索引对应的是:有效子字符串的前一位字符的索引值,用示例 1 来解释下:
"(()"
按照前面的方法,实现的过程如下(stack 表示栈,i 为遍历时的索引值):
- 先将
-1
压入栈中,那么stack = [-1]
。 - 开始遍历,先遇到
(
,索引压入栈中,stack = [-1, 0], i = 0
; - 继续遍历,还是
(
,索引入栈,stack=[-1, 0, 1], i = 1
; - 最后,遇到的是
)
,将栈顶元素出栈,stack=[-1, 0], i = 2
,这个时候,计算最大有效长度:当前字符索引减去栈顶元素的索引,也就是len = 2-0
。此时这个栈顶元素 0,就是最开始的(
第一个左括号对应的索引。
至于为什么要先将 -1
压入栈中,这里举例解释下:
"()"
如果遇到的是这样的字符串,那么按照上面的实现过程,当遍历结束后,栈是空。那么计算最大有效长度便会出错。如果事先将 -1
压入栈中,那么此时栈中的元素为 stack=[-1]
,那么这里可以计算出结果。
再举一个例子:
")()"
在这个字符串中,如果先遇到的是 )
,那么需要先进行出栈操作,这里如果栈中没有元素,这里同样会报错。
具体的实现代码如下。
代码实现
class Solution:
def longestValidParentheses(self, s: str) -> int:
max_len = 0
stack = []
# 当先遇到 `)` 需要先弹出元素,这里可以防止报错
# 当遇到的 `()` 的字符时,-1 在计算长度的时候,发挥作用
stack.append(-1)
for i in range(len(s)):
if s[i] == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
max_len = max(max_len, i - stack[-1])
return max_len
实现结果
总结
- 因为要找出有效的括号,有可能会遇到括号由内往外扩展,这跟栈先入后出的特性相似,可以考虑使用栈的方法来解决;
- 首先使用暴力解的方法尝试解决问题,在这里,罗列出所有非空偶数子字符串,检查他的有效性,统计最大的有效长度(但是执行之后发现超时)
- 这里对暴力解进行优化,不使用罗列的方法。直接在遍历字符串的时候,检查遍历扫描的子字符串是否有效同时计算有效长度,具体的做法如下:
- 先将
-1
压入栈中(具体的原因前面已分析) - 当遇到
(
时,将其索引压入栈中, - 当遇到
)
时,出栈,计算有效长度(用当前遍历的字符索引减去此时栈顶元素)。 - 循环遍历,得到最大的有效长度。
- 先将
文章原创,如果觉得写得还可以,欢迎关注点赞。微信公众号《书所集录》同步更新,同样欢迎关注点赞。