[ LeetCode ] 题刷刷(Python)-第20题:有效的括号

题目描述

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

有效字符串需满足:

1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
3、每个右括号都有一个对应的相同类型的左括号。

示例

示例 1:

输入:s = "()"
输出:true
示例 2:

输入:s = "()[]{}"
输出:true
示例 3:

输入:s = "(]"
输出:false

解题

解法一: 栈辅助法

思路

利用栈数据结构的特点(后进先出,LIFO)来模拟括号的匹配过程,确保遇到的每一个右括号都能找到对应的左括号。

  1. 遍历字符串:从左到右逐个遍历字符串中的每一个字符。
  2. 使用栈存储左括号:每当遇到一个左括号(如 '(', '[', or `'{``)时,将其压入栈中。栈用于暂存未匹配的左括号。
  3. 检查右括号与栈顶左括号的匹配性:当遇到一个右括号(如 ')', ']', or '}')时,检查栈是否为空以及栈顶元素是否与当前右括号匹配。若栈非空且栈顶元素与当前右括号匹配,则弹出栈顶元素;否则,字符串无效,返回 False。
  4. 遍历结束后的判断:遍历完整个字符串后,若栈为空,说明所有左括号都已经找到对应的右括号,字符串有效,返回 True;否则,栈中仍有未匹配的左括号,字符串无效,返回 False。

算法复杂度

时间复杂度:O(n),其中 n 为字符串 s 的长度。

由于函数对字符串 s 中的每个字符均进行一次操作,因此,该函数的时间复杂度为 O(n),其中 n 为字符串 s 的长度。


空间复杂度:O(n),其中 n 为字符串 s 的长度。

函数使用了一个栈 stack 存储遍历过程中遇到的左括号。在最坏情况下,即字符串 s 中的所有括号都是有效配对的,栈中最多存储与字符串长度相等的左括号。

代码

class Solution:def isValid(self, s: str) -> bool:# 定义一个字典,用于映射左括号到对应的右括号opening_brackets = {'(': ')', '[': ']', '{': '}'}# 初始化一个空栈,用于存储遇到的左括号stack = []# 遍历输入字符串中的每一个字符for char in s:# 当前字符为左括号时,将其压入栈中if char in opening_brackets:stack.append(char)# 当前字符为右括号,且栈非空且栈顶元素与当前右括号匹配时,# 弹出栈顶元素(表示找到了一个有效的括号对)elif stack and char == opening_brackets[stack[-1]]:stack.pop()# 当前字符为右括号,但与栈顶左括号不匹配时,字符串无效,提前返回 Falseelse:return False# 遍历完整个字符串后,若栈为空,说明所有左括号都已经找到对应的右括号,字符串有效,返回 True# 若栈不为空,说明还有未匹配的左括号,字符串无效,返回 Falsereturn not stack

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/312416.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【C++】stack与queue(相关接口介绍、容器适配器、deque、模拟实现)

一、stack 1.1 stack介绍 stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行 元素的插入与提取操作。stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供…

Go 单元测试之HTTP请求与API测试

文章目录 一、httptest1.1 前置代码准备1.2 介绍1.3 基本用法 二、gock2.1介绍2.2 安装2.3 基本使用2.4 举个例子2.4.1 前置代码2.4.2 测试用例 一、httptest 1.1 前置代码准备 假设我们的业务逻辑是搭建一个http server端,对外提供HTTP服务。用来处理用户登录请求…

网红泡泡机单片机方案开发定制

酷得(i-coder)是一家专业的技术服务公司,致力于为各类智能硬件提供高效、稳定、安全的底层驱动解决方案。我们拥有一支经验丰富、技术精湛的团队,能够为客户提供全方位的底层驱动开发服务。 下面是酷得的开发流程: 1…

记录一次k8s pod之间ip无法访问,问题排查与定位

记录一次k8s pod之间ip无法访问,问题排查与定位 问题展现现象 node之间通信正常 部分node上的pod无法通信 排查有问题node 使用启动网络测试工具 环境准备 docker 数据库mysql 使用有状态副本集合 --- apiVersion: apps/v1 kind: StatefulSet metadata:anno…

Win10本地更新无法升级win11 的0x80080005解决方法

Win10本地更新无法升级win11 Visual Studio 2022 运行项目时,本文提供了错误“指定的程序需要较新版本的 Windows”的解决方法。 更新时提示:0x80080005 解决方法 1、下载Windows11InstallationAssistant.exe 【免费】Windows11InstallationAssista…

基于GAN的图像补全实战

数据与代码地址见文末 论文地址:http://iizuka.cs.tsukuba.ac.jp/projects/completion/data/completion_sig2017.pdf 1.概述 图像补全,即补全图像中的覆盖和缺失部分, 网络整体结构如下图所示,整体网络结构还是采取GAN,对于生成器,网络结构采取Unet的形式,首先使用卷积…

高级数据结构与算法(8)

一、选择题 1、Rod-cutting Problem: Given a rod of total length N inches and a table of selling prices PL​ for lengths L=1,2,⋯,M. You are asked to find the maximum revenue RN​ obtainable by cutting up the rod and selling the pieces. For example, based o…

SpringBoot和Axios数据的传递和接收-Restful完全版

文章目录 一、基础知识铺垫Axios使用HTTP请求方式数据传输方式SpringBoot获取数据的方式 二、基础传递代码示例(一)Path Variables(二)Get、DeleteRequestParamModelAttribute (三)Post、Put、PatchRequest…

2024年五一杯数学建模B题思路分析

文章目录 1 赛题思路2 比赛日期和时间3 组织机构4 建模常见问题类型4.1 分类问题4.2 优化问题4.3 预测问题4.4 评价问题 5 建模资料 1 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 2 比赛日期和时间 报名截止时间:2024…

DataX案例,MongoDB数据导入HDFS与MySQL

【尚硅谷】Alibaba开源数据同步工具DataX技术教程_哔哩哔哩_bilibili 目录 1、MongoDB 1.1、MongoDB介绍 1.2、MongoDB基本概念解析 1.3、MongoDB中的数据存储结构 1.4、MongoDB启动服务 1.5、MongoDB小案例 2、DataX导入导出案例 2.1、读取MongoDB的数据导入到HDFS 2…

期货开户只要跟随于市场即可

仓,和时间无关;和价格运动的距离长短也很少关联,如果有的话,就是看价格运动的边界是否已经到达或准备穿越,价格运动的边界,其实很好辨认(说的好,精辟)。十五分钟以上图形…

分类预测 | Matlab实现RIME-LSSVM霜冰算法优化最小二乘支持向量机数据分类预测

分类预测 | Matlab实现RIME-LSSVM霜冰算法优化最小二乘支持向量机数据分类预测 目录 分类预测 | Matlab实现RIME-LSSVM霜冰算法优化最小二乘支持向量机数据分类预测分类效果基本介绍程序设计参考资料 分类效果 基本介绍 1.Matlab实现RIME-LSSVM霜冰算法优化最小二乘支持向量机数…

机器学习和深度学习--李宏毅(笔记与个人理解)Day9

Day9 Logistic Regression(内涵,熵和交叉熵的详解) 中间打了一天的gta5,图书馆闭馆正好npy 不舒服那天天气不好,哈哈哈哈哈总之各种理由吧,导致昨天没弄起来,今天补更! 这里重点注意…

【植物大战僵尸融合机器学习】+源码

上期回顾: 今天给大家推荐一个Gtihub开源项目:PythonPlantsVsZombies,翻译成中就是植物大战僵尸。 《植物大战僵尸》是一款极富策略性的小游戏。可怕的僵尸即将入侵,每种僵尸都有不同的特点,例如铁桶僵尸拥有极强的抗…

【Android AMS】startActivity流程分析

文章目录 AMSActivityStackstartActivity流程startActivityMayWaitstartActivityUncheckedLocked startActivityLocked(ActivityRecord r, boolean newTask, boolean doResume, boolean keepCurTransition)resumeTopActivityLocked 参考 AMS是个用于管理Activity和其它组件运行…

网络靶场实战-PE 自注入

默认的 Windows API 函数(LoadLibrary、LoadLibraryEx)只能加载文件系统中的外部库,无法直接从内存中加载 DLL,并且无法正确地加载 EXE。有时候,确实需要这种功能(例如,不想分发大量文件或者想增…

API管理平台:你用的到底是哪个?

Apifox是不开源的,在github的项目只是readme文件,私有化需要付费。当然saas版目前是免费使用的。 一、Swagger 为了让Swagger界面更加美观,有一些项目可以帮助你实现这一目标。以下是一些流行的项目,它们提供了增强的UI和额外的功…

Axure中继器排序失效 /没变化解决

问题复现 通过设置交互条件后,但是没效果,查了很多资料,按照教程操作,仍旧没效果。 原因 结论先行:问题出在汉化包,你用了汉化包导致axure内部出错。最简单的办法,删除汉化文件,…

AI应用实战2:使用scikit-learn进行回归任务实战

代码仓库在gitlab,本博客对应于02文件夹。 1.问题分析 在此篇博客中我们来对回归任务进行实战演练,背景是直播带货平台的业绩预测。第一步,就是分析问题。 问题痛点: 在直播带货平台上,由于市场环境多变、用户行为复…

SSH协议的优缺点

SSH(Secure Shell)是一种用于在计算机网络上进行安全远程访问和执行命令的协议。提供加密通信通道,防止敏感信息在传输过程中被窃听或篡改。SSH还支持文件传输和端口转发等功能,使其成为广泛使用的安全远程管理工具。 1. 安全远程…