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

【算法】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 检查替换后的词是否有效问题描述&#xff1a;分析代码 Tag Check If Word Is Valid After Substitutions 检查替换后的词是否有效 问题描述&#xff1a; 给你一个字符串 s &#xff0c;请你判断它是否 有效 。 字符串 s…...

基于jenkinsfile布置java工程

需求 通过jenkins发布java项目到服务器 预备环境 项目地址&#xff1a; https://gitee.com/asaland/sb-docker-appJenkins 2.387.3 通过Jenkinsfile实现方式 jenkins ui 配置pipeline 什么是pipeline? 直接看注释吧&#xff0c;简单点就是编排可以多个跨时间的构建代理…...

Spring JpaTransactionManager事务管理

首先&#xff0c;在做关于JpaTransactionManager之前&#xff0c;先对Jpa做一个简单的了解&#xff0c;他毕竟不如hibernate那么热门&#xff0c;其实二者很相识&#xff0c;只不过后期hibernate和JDO 版本都已经兼容了其Jpa&#xff0c;目前大家用的少了。 JPA全称Java Persi…...

全国职业院校技能大赛网络建设与运维赛项赛题(七)

全国职业院校技能大赛 网络建设与运维 赛题 (七)...

asp.net+sqlserver企业公司进销存管理系统

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

WxGL应用实例:绘制点云

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

一个月内面了30家公司,薪资从18K变成28K,真行啊····

工作3年&#xff0c;换了好几份工作&#xff08;行业流行性大&#xff09;&#xff0c;每次工作都是裸辞。朋友都觉得不可思议。因为我一直对自己很有信心&#xff0c;而且特别不喜欢请假面试&#xff0c;对自己负责也对公司负责。 但是这次没想到市场环境非常不好&#xff0c;…...

《计算机网络——自顶向下方法》精炼——1.4到1.7

三更灯火五更鸡&#xff0c;努力学习永不止。无惧困难与挑战&#xff0c;砥砺前行向成功。 文章目录 引言正文时延排队时延 吞吐量协议层次&#xff0c;服务模型&#xff08;重点&#xff09;封装&#xff08;重点&#xff09;网络安全&#xff08;选看&#xff09;恶意软件的分…...

消息队列 (Message Queue)

消息队列 What 消息队列 是消息的队列&#xff1b;是消息的临时缓冲&#xff1b;是发布/订阅模式的兄弟&#xff1b;在多个进程/线程间实现异步通讯模式。 Why 消息队列在多个进程/线程中实现了异步通讯模式。 这里我们先介绍下同步消息处理。对于同步消息处理&#xff0…...

JavaScript原型链污染学习记录

1.JS原型和继承机制 0> 原型及其搜索机制 NodeJS原型机制&#xff0c;比较官方的定义&#xff1a; 我们创建的每个函数都有一个 prototype&#xff08;原型&#xff09;属性&#xff0c;这个属性是一个指针&#xff0c;指向一个对象&#xff0c; 而这个对象的用途是包含可…...

顶级白帽黑客必备的十大黑客技术

1.熟悉Linux系统和命令行操作&#xff1a; Linux是黑客的基石&#xff0c;几乎所有黑客工具和技术都是在Linux平台上运行的&#xff0c;熟悉Linux系统和命令行操作是必须的。 2.掌握网络协议和TCP/IP模型&#xff1a; 了解TCP/IP模型、网络协议和通信流程是黑客攻击的基础&a…...

【关于认证鉴权一些概念梳理】

关于认证鉴权一些概念梳理 记录一些灵感瞬间聊聊Session&#xff0c;Cookie和Token三剑客的特性前后端分离登录中的springsecurity与不分离的异同三更up关于springSecurity的讲解B站知乎上关于springSecurity的讲解掘金大佬SpringSecurityJWT认证流程解析一个权限对应一个资源&…...

16.网络爬虫—字体反爬(实战演示)

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

BOM概述

目录 什么是BOM 浏览器对象模型&#xff08;Browser Object Model (BOM)&#xff09; 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 微服务虽然具备各种各样的优势&#xff0c;但服务的拆分通用给部署带来了很大的麻烦。 分布式系统中&#xff0c;依赖的组件非常多&#xff0c;不同组件之间部署时往往会产生一些冲突。在数百上千台服务中重复部署…...

群体无人机:协同作战的未来

摘要&#xff1a;本文将探讨群体无人机技术的发展及其在多个领域的应用&#xff0c;特别是在军事作战、救援任务和物流方面的潜力。我们将分析群体无人机在协同作战中的优势&#xff0c;以及如何通过协同控制和通信技术实现更高效的任务完成。 内容&#xff1a; 引言 简要介绍…...

如何在Windows AD域中驻留ACL后门

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

LVGL移植——stm32f4

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

ASEMI代理ADP5054ACPZ-R7原装ADI车规级ADP5054ACPZ-R7

编辑&#xff1a;ll ASEMI代理ADP5054ACPZ-R7原装ADI车规级ADP5054ACPZ-R7 型号&#xff1a;ADP5054ACPZ-R7 品牌&#xff1a;ADI/亚德诺 封装&#xff1a;LFCSP-48 批号&#xff1a;2023 引脚数量&#xff1a;48 工作温度&#xff1a;-40C~125C 安装类型&#xff1a;表…...

TCP/IP相关面试题

1. 什么是TCP/IP协议&#xff1f;它的作用是什么&#xff1f; TCP/IP&#xff08;Transmission Control Protocol/Internet Protocol&#xff09;互联网中最常用的协议&#xff0c;是计算机网络通信的基础。由TCP协议和IP协议两部分组成。IP协议负责数据的传输和路由选择&#…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

Mac软件卸载指南,简单易懂!

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

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会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;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…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...

WEB3全栈开发——面试专业技能点P4数据库

一、mysql2 原生驱动及其连接机制 概念介绍 mysql2 是 Node.js 环境中广泛使用的 MySQL 客户端库&#xff0c;基于 mysql 库改进而来&#xff0c;具有更好的性能、Promise 支持、流式查询、二进制数据处理能力等。 主要特点&#xff1a; 支持 Promise / async-await&#xf…...