当前位置: 首页 > news >正文

leetcode - 678. Valid Parenthesis String

Description

Given a string s containing only three types of characters: ‘(’, ‘)’ and ‘*’, return true if s is valid.

The following rules define a valid string:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "(*)"
Output: true

Example 3:

Input: s = "(*))"
Output: true

Constraints:

1 <= s.length <= 100
s[i] is '(', ')' or '*'.

Solution

Stack

Use 2 stacks, one for opening parenthesis, one for stars. When the current character is a closing parenthesis, pop from the opening parenthesis first, then the star. After iterating the string, pop from the opening parenthesis and star, for every opening parenthesis, if there is a star at the right, then it’s valid.

Time complexity: o ( n ) o(n) o(n)
Space complexity: o ( n ) o(n) o(n)

Two pointers

Solved after help.

Use cmin to denote the count of ( we must pair, and cmax to denote the count of ( at most we need to pair. So when the current character is (, we increase both of them by 1, when it’s ) we decrease by 1, when it’s *, we decrease cmin by 1 (the star will work as )), and increase cmax by 1 (the star will work as ().

During this process, the cmax can’t be negative, and in the end, the cmin needs to be 0.

Here’s a graph from this solution:
在这里插入图片描述
Time complexity: o ( n ) o(n) o(n)
Space complexity: o ( 1 ) o(1) o(1)

Code

Stack

class Solution:def checkValidString(self, s: str) -> bool:star_stack = []opening_stack = []for i, each_c in enumerate(s):if each_c == '(':opening_stack.append(i)elif each_c == ')':if opening_stack:opening_stack.pop()elif star_stack:star_stack.pop()else:return Falseelse:star_stack.append(i)while opening_stack:if not star_stack:return Falseopening_i, star_i = opening_stack.pop(), star_stack.pop()if star_i < opening_i:return Falsereturn True

Two pointers

class Solution:def checkValidString(self, s: str) -> bool:cmin, cmax = 0, 0for each_c in s:if each_c == '(':cmin += 1cmax += 1elif each_c == ')':cmin -= 1cmax -= 1else:cmin -= 1cmax += 1if cmax < 0:return Falsecmin = max(0, cmin)return cmin == 0

相关文章:

leetcode - 678. Valid Parenthesis String

Description Given a string s containing only three types of characters: ‘(’, ‘)’ and ‘*’, return true if s is valid. The following rules define a valid string: Any left parenthesis ( must have a corresponding right parenthesis ). Any right parenth…...

索尼相机照片清理软件

在使用索尼相机拍摄照片的时候有时我们需要同时拍摄JPG格式和RAW格式&#xff0c;这在后期选图的时候给我们带来一些麻烦。我们固然可以选用Br来管理照片&#xff0c;但是现在我们可以有一个更轻量的软件&#xff08;8.8MB&#xff09;来做到一部分功能。 我们将照片从SD卡导出…...

比赛记录:Codeforces Global Round 25 A~E (猜猜题场)

传送门:CF [前题提要]:其实这场打的不是很好.A题一个sb错误看不出来,50min后才过,B题上来就Wa了一发,C题用了没必要的线段树,D题刚开始被60诈骗,一直在想按位考虑.幸好赛时猜出了E,然后又猜出来D,本来掉大分变成上大分…但是这场前几题大都是猜猜题,所以本来不想写题解的.但是…...

Windows系统安装OpenSSH结合VS Code远程ssh连接Ubuntu【内网穿透】

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法|MySQL| ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-AwzyR2lkHKjD9HYl {font-family:"trebuchet ms",verdana,arial,sans-serif;f…...

Svg Flow Editor 原生svg流程图编辑器(五)

系列文章 Svg Flow Editor 原生svg流程图编辑器&#xff08;一&#xff09; Svg Flow Editor 原生svg流程图编辑器&#xff08;二&#xff09; Svg Flow Editor 原生svg流程图编辑器&#xff08;三&#xff09; Svg Flow Editor 原生svg流程图编辑器&#xff08;四&#xf…...

数字晶体管选型参数,结构原理,工艺与注意问题总结

🏡《总目录》 目录 1,概述2,工作原理2.1,AND 门(与门),2.2,OR 门(或门):2.3,NOT 门(非门):2.4,NAND 门(与非门):2.5,NOR 门(或非门):3,结构特点3.1,TTL(Transistor-Transistor Logic)晶体管...

lua学习笔记9(字典的学习)

print("********************字典的学习***********************") a{["凌少"]"傻逼",["我"]"天才",["age"]24,["daihao"]114514,["8848"]20000} --访问单个变量 print(a["凌少"])…...

第六篇: 3.5 性能效果 (Performance)- IAB/MRC及《增强现实广告效果测量指南1.0》

​​​​​​​ 翻译计划 第一篇概述—IAB与MRC及《增强现实广告效果测量指南》之目录、适用范围及术语第二篇 广告效果测量定义和其他矩阵之- 3.1 广告印象&#xff08;AD Impression&#xff09;第三篇 广告效果测量定义和其他矩阵之- 3.2 可见性 &#xff08;Viewability…...

mysql学习笔记NO.2

Java操作数据库、表笔记 1.创建数据库 创建数据库的步骤如下&#xff1a; 导入所需的Java数据库连接驱动&#xff08;如MySQL驱动&#xff09;。使用JDBC连接到数据库。执行SQL语句创建数据库。 import java.sql.Connection; import java.sql.DriverManager; import java.…...

C++11:lambda表达式 包装器

C11&#xff1a;lambda表达式 & 包装器 lambda表达式包装器functionbind lambda表达式 在C98中&#xff0c;如果想对一个结构体数组使用sort排序&#xff0c;那么我们就需要自己些仿函数。 比如以下结构体&#xff1a; struct Goods {string _name; // 名字double _pric…...

Node.js HTTP/2 CONTINUATION 拒绝服务漏洞(CVE-2024-27983)

Node.js 是开源、跨平台的 JavaScript 运行时环境。CONTINUATION泛洪攻击被发现存在于多个HTTP/2协议实现中。 在受影响版本中&#xff0c;由于Node.js针对HTTP/2协议的实现不当&#xff0c;未正确处理多个CONTINUATION帧的情况&#xff0c;在node::http2::Http2Session::~Htt…...

YOLOV8 + 双目测距

YOLOV8 双目测距 1. 环境配置2. 测距流程和原理2.1 测距流程2.2 测距原理 3. 代码部分解析3.1 相机参数stereoconfig.py3.2 测距部分3.3 主代码yolov8-stereo.py 4. 实验结果4.1 测距4.2 测距跟踪4.3 测距跟踪分割4.4 视频展示 相关文章 1. YOLOv5双目测距&#xff08;python&…...

前端:SVG绘制流程图

效果 代码 html代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><title>SVG流程图示例</title><style>/* CSS 样式 */</style><script src"js/index.js"></script…...

【Linux系列】如何确定当前运行的是 RHEL 9 还是 RHEL 8?

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…...

vscode开发java的插件和配置

推荐插件 .vscode/extensions.json {"recommendations": ["redhat.fabric8-analytics","ms-azuretools.vscode-docker","vscjava.vscode-java-pack","eamodio.gitlens","obkoro1.korofileheader","redhat.j…...

Mysql启动报错:本地计算机上的mysql服务启动后停止,某些服务在未由其他服务或程序使用时将自动停止

Mysql启动报错&#xff1a;本地计算机上的mysql服务启动后停止,某些服务在未由其他服务或程序使用时将自动停止 文章目录 Mysql启动报错&#xff1a;本地计算机上的mysql服务启动后停止,某些服务在未由其他服务或程序使用时将自动停止1. 备份mysql的data文件夹2. 重新构建 Wind…...

WPF程序添加托盘图标

程序添加托盘图标 UI层 //添加handycontrol的引用xmlns:hc"https://handyorg.github.io/handycontrol"//添加NotifyIcon图标 实现单击 双击 二级菜单点击功能<hc:NotifyIconText"通知"Token"Info"><hc:NotifyIcon.ContextMenu><…...

工业4g路由器联网后迅速掉线是什么原因?

工业4G路由器连接上网后迅速掉线可能是由多种因素造成的。以下是一些建议的检查和解决步骤&#xff1a; 1、信号问题&#xff1a; 信号强度&#xff1a;检查工业路由器信号强度指示灯&#xff0c;如果信号弱&#xff0c;尝试移动路由器位置或添加外部天线来增强信号。 网络拥…...

腾讯云4核8G服务器12M带宽646元1年零3个月,4C8G使用场景说明

腾讯云4核8G服务器多少钱&#xff1f;腾讯云4核8G轻量应用服务器12M带宽租用价格646元15个月&#xff0c;活动页面 txybk.com/go/txy 活动链接打开如下图所示&#xff1a; 腾讯云4核8G服务器优惠价格 这台4核8G服务器是轻量应用服务器&#xff0c;详细配置为&#xff1a;轻量4核…...

java - 读取配置文件

文章目录 1. properties2. XML(1) dom4j(2) XPath 1. properties // 创建properties对象用于读取properties文件Properties properties new Properties();properties.load(new FileReader("src/main/resources/test.properties"));String name properties.getPrope…...

React 第五十五节 Router 中 useAsyncError的使用详解

前言 useAsyncError 是 React Router v6.4 引入的一个钩子&#xff0c;用于处理异步操作&#xff08;如数据加载&#xff09;中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误&#xff1a;捕获在 loader 或 action 中发生的异步错误替…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...