当前位置: 首页 > 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协议负责数据的传输和路由选择&#…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

Swagger和OpenApi的前世今生

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

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...