开发面试题 反射 overflow 哨兵模式 莱斯分布 Android开发 haskell matrix graph encoding collections arduino joomla progressjs vue状态管理 后台模板 网络营销视频教程 seo计费系统 jquery解析json数据 kafka消费不到数据 websocket库 maven插件 nfc卡片 xshell搭建ss pyhton中异常和模块 linux查询文件内容 kubernetes实战 mysql学习 python中的zip python指令 python插件 java基础类型 javapattern java时间戳转时间 java中的数据结构 java索引 linuxtar命令 嵌入式linux驱动程序设计从入门到精通 unix操作系统下载 圣剑世界
当前位置: 首页 > 学习教程  > python

【Leetcode】20. 有效的括号(Valid Parentheses)

2021/2/7 11:06:09 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

No20. 有效的括号 题目 给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。左括号必须以正确的顺…

No20. 有效的括号

题目

给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1

  • 输入: “()”
  • 输出: true

示例 2

  • 输入: “()[]{}”
  • 输出: true

示例 3

  • 输入: “(]”
  • 输出: false

示例 4

比较重要

  • 输入: “([)]”
  • 输出: false

示例 5

  • 输入: “{[]}”
  • 输出: true

提示

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成

解题代码(Python3)

class Solution:
    def isValid(self, s: str) -> bool:
        #栈
        stack = []
        pattern_dict = dict(zip(list(')]}'),list('([{')))
        for x in s:
        	#如果是左括号,直接入栈
            if x in pattern_dict.values():
                stack += x
            else:
                if len(stack) == 0:
                    return False
                if stack[-1] == pattern_dict[x]:
                    #这里pop是O(1)
                    stack.pop()
                else:
                    return False
        #最后注意要对栈进行检查
        return True if len(stack) == 0 else False

在这里插入图片描述

思路:

利用栈去做匹配,左括号直接入栈;右括号要进行判别,如果与栈顶元素与该右括号匹配,则栈顶元素进行出栈,否则直接返回False。

另外在循环后,要对栈进行判空操作。

复杂度分析:

  • 时间复杂度O(n/2) = O(n)
  • 空间复杂度O(1)

其他想法:

在这里插入图片描述

如果使用del stack[-1],那么时间复杂度会变为O(n^2),验证效果如下:
在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_2000242.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?