LeetCode 32. 最长有效括号 | Python

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 压入栈中(具体的原因前面已分析)
    • 当遇到 ( 时,将其索引压入栈中,
    • 当遇到 ) 时,出栈,计算有效长度(用当前遍历的字符索引减去此时栈顶元素)。
    • 循环遍历,得到最大的有效长度。

文章原创,如果觉得写得还可以,欢迎关注点赞。微信公众号《书所集录》同步更新,同样欢迎关注点赞。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,921评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 87,635评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 151,393评论 0 338
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,836评论 1 277
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,833评论 5 368
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,685评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,043评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,694评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 42,671评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,670评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,779评论 1 332
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,424评论 4 321
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,027评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,984评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,214评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,108评论 2 351
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,517评论 2 343