当前位置: 首页 > 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…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

Django RBAC项目后端实战 - 03 DRF权限控制实现

项目背景 在上一篇文章中&#xff0c;我们完成了JWT认证系统的集成。本篇文章将实现基于Redis的RBAC权限控制系统&#xff0c;为系统提供细粒度的权限控制。 开发目标 实现基于Redis的权限缓存机制开发DRF权限控制类实现权限管理API配置权限白名单 前置配置 在开始开发权限…...

2025-05-08-deepseek本地化部署

title: 2025-05-08-deepseek 本地化部署 tags: 深度学习 程序开发 2025-05-08-deepseek 本地化部署 参考博客 本地部署 DeepSeek&#xff1a;小白也能轻松搞定&#xff01; 如何给本地部署的 DeepSeek 投喂数据&#xff0c;让他更懂你 [实验目的]&#xff1a;理解系统架构与原…...

RLHF vs RLVR:对齐学习中的两种强化方式详解

在语言模型对齐&#xff08;alignment&#xff09;中&#xff0c;强化学习&#xff08;RL&#xff09;是一种重要的策略。而其中两种典型形式——RLHF&#xff08;Reinforcement Learning with Human Feedback&#xff09; 与 RLVR&#xff08;Reinforcement Learning with Ver…...