【算法】Check If Word Is Valid After Substitutions 检查替换后的词是否有效
文章目录
- Check If Word Is Valid After Substitutions 检查替换后的词是否有效
- 问题描述:
- 分析
- 代码
- Tag
Check If Word Is Valid After Substitutions 检查替换后的词是否有效
问题描述:
给你一个字符串 s ,请你判断它是否 有效 。
字符串 s 有效 需要满足:假设开始有一个空字符串 t = “” ,你可以执行 任意次 下述操作将 t 转换为 s :
将字符串 “abc” 插入到 t 中的任意位置。形式上,t 变为 tleft + “abc” + tright,其中 t == tleft + tright 。注意,tleft 和 tright 可能为 空 。
如果字符串 s 有效,则返回 true;否则,返回 false。
s.length范围[1,20000],仅由abc构成。
分析
使用暴力构造的方法,就是每构造一个有效的s’,然后在s’的每个位置上插入abc,直到达到目标的s长度。但是s’越长,枚举的位置越多,时间复杂度也越大。
同样逆向的做dfs,每次找到一个abc,然后删除,但是这样也会面临相同的问题。
还有一种暴力的思路,就是replace,每一次将所有符合条件的abc,全部用空字符串替换,直到整个s,不存在abc,判断s是否是空字符串。
replace作为封装的string API,确实可以处理这个问题,但是另一方面,这个replace过程中对空间,时间上的消耗,可以思考一下。
这个问题可以抽象成为一个栈,类似于括号匹配。abc可以抽象的作为一个(),遇到字符a,可以直接入栈。遇到字符b,如果要符合条件,那么此时栈顶必须是a,也就是说,如果栈空或者栈顶!=a,说明无法满足题目的条件,返回false。否则可以将栈顶修改为b。遇到字符c,其实和字符b是一样的处理,也是只关心栈顶是否是b。
整个流程遍历一次,最大的空间就是开栈,时间复杂度ON,空间ON。
时间复杂度 O(N)
空间复杂度: O(N)
代码
public boolean isValid(String s) {while(s.indexOf("abc")!=-1){s = s.replace("abc","");}return s.equals("");}
时间复杂度 O(N)
空间复杂度: O(N)
public boolean isValid(String s) {Deque<Integer> st = new ArrayDeque();for(int i=0;i<s.length();i++){int c = s.charAt(i)-'a';if(c==0){st.push(c);continue;}if(st.isEmpty()) return false;int top = st.pop();if(c-top!=1)return false;if(c==1){st.push(c);} } return st.isEmpty(); }
代码还可以再压缩,但是基本流程是这样。
Tag
栈
相关文章:
【算法】Check If Word Is Valid After Substitutions 检查替换后的词是否有效
文章目录 Check If Word Is Valid After Substitutions 检查替换后的词是否有效问题描述:分析代码 Tag Check If Word Is Valid After Substitutions 检查替换后的词是否有效 问题描述: 给你一个字符串 s ,请你判断它是否 有效 。 字符串 s…...

基于jenkinsfile布置java工程
需求 通过jenkins发布java项目到服务器 预备环境 项目地址: https://gitee.com/asaland/sb-docker-appJenkins 2.387.3 通过Jenkinsfile实现方式 jenkins ui 配置pipeline 什么是pipeline? 直接看注释吧,简单点就是编排可以多个跨时间的构建代理…...
Spring JpaTransactionManager事务管理
首先,在做关于JpaTransactionManager之前,先对Jpa做一个简单的了解,他毕竟不如hibernate那么热门,其实二者很相识,只不过后期hibernate和JDO 版本都已经兼容了其Jpa,目前大家用的少了。 JPA全称Java Persi…...
全国职业院校技能大赛网络建设与运维赛项赛题(七)
全国职业院校技能大赛 网络建设与运维 赛题 (七)...

asp.net+sqlserver企业公司进销存管理系统
基于WEB的进销存管理系统主要企业内部提供服务,系统分为管理员,和员工2部分。 在本基于WEB的进销存管理系统中分为管理员,和普通用户2中模式,其中管理人员主要是对企业内商品类型。商品信息商品的出入库信息,以及员工…...

WxGL应用实例:绘制点云
WxGL附带了几个工具函数,其中read_pcfile用来解析.ply和.pcd格式的点云文件,该函数返回一个PointCloudData类实例,包含以下属性: PointCloudData.ok - 数据是否可用,布尔型PointCloudData.info - 数据可用性说明&…...

一个月内面了30家公司,薪资从18K变成28K,真行啊····
工作3年,换了好几份工作(行业流行性大),每次工作都是裸辞。朋友都觉得不可思议。因为我一直对自己很有信心,而且特别不喜欢请假面试,对自己负责也对公司负责。 但是这次没想到市场环境非常不好,…...

《计算机网络——自顶向下方法》精炼——1.4到1.7
三更灯火五更鸡,努力学习永不止。无惧困难与挑战,砥砺前行向成功。 文章目录 引言正文时延排队时延 吞吐量协议层次,服务模型(重点)封装(重点)网络安全(选看)恶意软件的分…...
消息队列 (Message Queue)
消息队列 What 消息队列 是消息的队列;是消息的临时缓冲;是发布/订阅模式的兄弟;在多个进程/线程间实现异步通讯模式。 Why 消息队列在多个进程/线程中实现了异步通讯模式。 这里我们先介绍下同步消息处理。对于同步消息处理࿰…...

JavaScript原型链污染学习记录
1.JS原型和继承机制 0> 原型及其搜索机制 NodeJS原型机制,比较官方的定义: 我们创建的每个函数都有一个 prototype(原型)属性,这个属性是一个指针,指向一个对象, 而这个对象的用途是包含可…...

顶级白帽黑客必备的十大黑客技术
1.熟悉Linux系统和命令行操作: Linux是黑客的基石,几乎所有黑客工具和技术都是在Linux平台上运行的,熟悉Linux系统和命令行操作是必须的。 2.掌握网络协议和TCP/IP模型: 了解TCP/IP模型、网络协议和通信流程是黑客攻击的基础&a…...
【关于认证鉴权一些概念梳理】
关于认证鉴权一些概念梳理 记录一些灵感瞬间聊聊Session,Cookie和Token三剑客的特性前后端分离登录中的springsecurity与不分离的异同三更up关于springSecurity的讲解B站知乎上关于springSecurity的讲解掘金大佬SpringSecurityJWT认证流程解析一个权限对应一个资源&…...

16.网络爬虫—字体反爬(实战演示)
网络爬虫—字体反爬 一字体反爬原理二字体反爬模块FonttoolsTTF文件 三FontCreator 14.0.0.2790FontCreatorPortable下载与安装 四实战演示五后记 前言: 🏘️🏘️个人简介:以山河作礼。 🎖️🎖️:Python领域…...

BOM概述
目录 什么是BOM 浏览器对象模型(Browser Object Model (BOM)) Window对象 一些常用方法 JavaScript Window Screen Window Screen Window Screen 高度 Window Screen 可用宽度 Window Screen 可用高度 Window Screen 色深 Window Screen 像素深…...

3.Docker实用技术
Docker实用篇 0.学习目标 1.初识Docker 1.1.什么是Docker 微服务虽然具备各种各样的优势,但服务的拆分通用给部署带来了很大的麻烦。 分布式系统中,依赖的组件非常多,不同组件之间部署时往往会产生一些冲突。在数百上千台服务中重复部署…...
群体无人机:协同作战的未来
摘要:本文将探讨群体无人机技术的发展及其在多个领域的应用,特别是在军事作战、救援任务和物流方面的潜力。我们将分析群体无人机在协同作战中的优势,以及如何通过协同控制和通信技术实现更高效的任务完成。 内容: 引言 简要介绍…...

如何在Windows AD域中驻留ACL后门
前言 当拿下域控权限时,为了维持权限,常常需要驻留一些后门,从而达到长期控制的目的。Windows AD域后门五花八门,除了常规的的添加隐藏用户、启动项、计划任务、抓取登录时的密码,还有一些基于ACL的后门。 ACL介绍 …...

LVGL移植——stm32f4
LVGL移植说明 移植LVGL版本:8.3.6 主控:STM32F407ZGT6 github链接:https://github.com/lvgl/lvgl.git 文章目录 LVGL移植说明STM32移植LVGL①需要的依赖文件②移植显示驱动文件③将文件加入工程当中④配置心跳④修改栈堆的空间⑤编译链接 STM…...

ASEMI代理ADP5054ACPZ-R7原装ADI车规级ADP5054ACPZ-R7
编辑:ll ASEMI代理ADP5054ACPZ-R7原装ADI车规级ADP5054ACPZ-R7 型号:ADP5054ACPZ-R7 品牌:ADI/亚德诺 封装:LFCSP-48 批号:2023 引脚数量:48 工作温度:-40C~125C 安装类型:表…...
TCP/IP相关面试题
1. 什么是TCP/IP协议?它的作用是什么? TCP/IP(Transmission Control Protocol/Internet Protocol)互联网中最常用的协议,是计算机网络通信的基础。由TCP协议和IP协议两部分组成。IP协议负责数据的传输和路由选择&#…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

循环冗余码校验CRC码 算法步骤+详细实例计算
通信过程:(白话解释) 我们将原始待发送的消息称为 M M M,依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)(意思就是 G ( x ) G(x) G(x) 是已知的)࿰…...

Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...

PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?
在工业自动化持续演进的今天,通信网络的角色正变得愈发关键。 2025年6月6日,为期三天的华南国际工业博览会在深圳国际会展中心(宝安)圆满落幕。作为国内工业通信领域的技术型企业,光路科技(Fiberroad&…...
vue3 daterange正则踩坑
<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...

实战设计模式之模板方法模式
概述 模板方法模式定义了一个操作中的算法骨架,并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下,重新定义算法中的某些步骤。简单来说,就是在一个方法中定义了要执行的步骤顺序或算法框架,但允许子类…...
WEB3全栈开发——面试专业技能点P4数据库
一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库,基于 mysql 库改进而来,具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点: 支持 Promise / async-await…...