Leetcode面试经典150题-97.交错字符串

给定三个字符串 s1s2s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 

子字符串

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意:a + b 意味着字符串 a 和 b 连接。

示例 1:

输入:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出:true

示例 2:

输入:s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出:false

示例 3:

输入:s1 = "", s2 = "", s3 = ""
输出:true

提示:

  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1s2、和 s3 都由小写英文字母组成

进阶:您能否仅使用 O(s2.length) 额外的内存空间来解决它?

其他的就不多说了,上代码,看不懂的请留言或者私信,收到第一时间解答

class Solution {public boolean isInterleave(String s1, String s2, String s3) {if(s1.length() + s2.length() != s3.length()) {return false;}/**都转成字符数组方便操作 */char[] s1Arr = s1.toCharArray();char[] s2Arr = s2.toCharArray();char[] s3Arr = s3.toCharArray();/**定义动态规划数组,dp[i][j]表示s1的前i个字符和s2的前j个字符能不能交错组成s3的前i+j个字符*/boolean[][] dp = new boolean[s1Arr.length+1][s2Arr.length+1];dp[0][0] = true;/**初始化第一行和第一列 */for(int i = 1; i < dp.length; i++) {dp[i][0] = dp[i-1][0] && s1Arr[i-1] == s3Arr[i-1];}for(int j = 1; j < dp[0].length; j++) {dp[0][j] = dp[0][j-1] && s2Arr[j-1]==s3Arr[j-1];}/**初始化一般情况 */for(int i = 1; i < dp.length; i++) {for(int j = 1; j < dp[i].length; j++) {dp[i][j] = (dp[i][j - 1] && s2Arr[j-1] == s3Arr[i+j-1]) || (dp[i-1][j] && s1Arr[i-1]==s3Arr[i+j-1]);}}/**返回结果:s1的前s1.length()个字符和s2的前s2.length个字符能不能组成s3*/return dp[s1Arr.length][s2Arr.length];}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/428508.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Springboot3 + MyBatis-Plus + MySql + Uniapp 实现商品规格选择sku(附带自设计数据库,最新保姆级教程)

Springboot3 MyBatis-Plus MySql Uniapp 实现商品规格选择sku&#xff08;附带自设计数据库&#xff0c;最新保姆级教程&#xff09; 1、效果展示2、数据库设计2.1 商品表2.2 商品价格和规格中间表2.3 商品规格表 3、后端代码3.1 model3.2 vo3.3 mapper、server、serverImp3…

使用express或koa或nginx部署history路由模式的单页面应用

使用hash模式会有#&#xff0c;影响美观&#xff0c;所以使用history模式会是个更好的选择。 前端项目打包上线部署&#xff0c;可以使用下面的方式部署history模式的项目&#xff0c;下面以 jyH5 为例 expressjs部署 express脚手架搭建的app.js中添加如下代码&#xff1a; …

CDA Level 1 业务数据分析

目录 理解业务数据分析方法、掌握业务数据分析流程、能够使用及设计创建业务指标、能够结合业务模型及业务分析方法正确理解业务问题&#xff0c;找到问题原因&#xff0c;并能够提出解决问题建议&#xff0c;这个章节的应用会考的比较多&#xff08;终于正经起来了呢&#xf…

设计模式 组合模式(Composite Pattern)

组合模式简绍 组合模式&#xff08;Composite Pattern&#xff09;是一种结构型设计模式&#xff0c;它允许你将对象组合成树形结构来表示“部分-整体”的层次结构。组合模式使得客户端可以用一致的方式处理单个对象和组合对象。这样&#xff0c;可以在不知道对象具体类型的条…

7--SpringBoot-后端开发、原理详解(面试高频提问点)

目录 SpringBoot原理 起步依赖 自动配置 配置优先级 Bean设置 获取Bean 第三方Bean SpringBoot原理 内容偏向于底层的原理分析 基于Spring框架进行项目的开发有两个不足的地方&#xff1a; 在pom.xml中依赖配置比较繁琐&#xff0c;在项目开发时&#xff0c;需要自己去找…

手写Spring

简单实现Spring基于注解配置 ComponentScan Target(ElementType.TYPE) Retention(RetentionPolicy.RUNTIME) public interface ComponentScan {String value() default ""; } 相当于component-scan HspSpringConfig ComponentScan(value "spring.write.com…

C#自定义曲线绘图面板

一、实现功能 1、显示面板绘制。 2、拖动面板&#xff0c;X轴、Y轴都可以拖动。 3、显示面板缩放&#xff0c;放大或者缩小。 4、鼠标在面板中对应的XY轴数值。 5、自动生成的数据数组&#xff0c;曲线显示。 6、鼠标是否在曲线上检测。 二、界面 拖动面板 鼠标在曲线上…

【随手笔记】使用J-LINK读写芯片内存数据

第一种使用JLINK.exe 1. 打开j-link.exe 2.输入【usb】 3. 连接芯片 输入【connect】输入芯片型号【STM32L071RB】输入连接方式 【S】 使用SWD连接方式输入连接速率 【4000】连接成功 4. 输入【&#xff1f;】查看指令提示 5. 读写指令 Mem Mem [<Zone>…

DataFrame生成excel后为什么多了一行数字

问题描述 python查询数据生成excel文件&#xff0c;生成的excel多了第一行数字索引&#xff0c;1,2,3,4,5...... 代码&#xff1a; df pd.DataFrame(data)df.to_excel(filename, sheet_name用户信息表, indexFalse) 解决&#xff1a; 原理也很简单&#xff0c;就是设置个参…

【python设计模式7】行为型模式2

目录 策略模式 模板方法模式 策略模式 定义一个个算法&#xff0c;把它们封装起来&#xff0c;并且使它们可以相互替换。本模式使得算法可独立于使用它的客户而变化。角色有&#xff1a;抽象策略、具体策略和上下文。 from abc import abstractmethod, ABCMeta from datetim…

前端vue-ref与document.querySelector的对比

ref只在本组件中查找&#xff0c;而document.querySelector是在整个页面查找

Golang | Leetcode Golang题解之第414题第三大的数

题目&#xff1a; 题解&#xff1a; func thirdMax(nums []int) int {var a, b, c *intfor _, num : range nums {num : numif a nil || num > *a {a, b, c &num, a, b} else if *a > num && (b nil || num > *b) {b, c &num, b} else if b ! ni…

SQL Server性能优化之读写分离

理论部分: 数据库读写分离&#xff1a; 主库&#xff1a;负责数据库操作增删改 20% 多个从库&#xff1a;负责数据库查询操作 80% 读写分离的四种模式 1.快照发布&#xff1a;发布服务器按照预定的时间间隔向订阅服务器发送已发布的数据快照 2.事务发布[比较主流常见]&#xf…

Ceph 基本架构(一)

Ceph架构图 Ceph整体组成 Ceph 是一个开源的分布式存储系统&#xff0c;设计用于提供优秀的性能、可靠性和可扩展性。Ceph 的架构主要由几个核心组件构成&#xff0c;每个组件都有特定的功能&#xff0c;共同协作以实现高可用性和数据的一致性。 以下是 Ceph 的整体架构及其…

2024 “华为杯” 中国研究生数学建模竞赛(C题)深度剖析|数据驱动下磁性元件的磁芯损耗建模|数学建模完整代码+建模过程全解全析

当大家面临着复杂的数学建模问题时&#xff0c;你是否曾经感到茫然无措&#xff1f;作为2022年美国大学生数学建模比赛的O奖得主&#xff0c;我为大家提供了一套优秀的解题思路&#xff0c;让你轻松应对各种难题&#xff01; CS团队倾注了大量时间和心血&#xff0c;深入挖掘解…

使用LangGPT提示词让大模型比较浮点数

使用LangGPT提示词让大模型比较浮点数 背景介绍环境准备创建虚拟环境安装一些必要的库安装其他依赖部署大模型启动图形交互服务设置提示词与测试 LangGPT结构化提示词 背景介绍 LLM在对比浮点数字时表现不佳&#xff0c;经验证&#xff0c;internlm2-chat-1.8b (internlm2-cha…

MySQL聚合统计和内置函数

【数据库】MySQL聚合统计 王笃笃-CSDN博客https://blog.csdn.net/wangduduniubi?typeblog显示平均工资低于2000的部门和它的平均工资 mysql> select deptno,avg(sal) deptavg from emp group by deptno; --------------------- | deptno | deptavg | --------------…

【第33章】Spring Cloud之SkyWalking服务链路追踪

文章目录 前言一、介绍1. 架构图2. SkyWalking APM 二、服务端和控制台1. 下载2. 解压3. 初始化数据库4. 增加驱动5. 修改后端配置6. 启动7. 访问控制台8. 数据库表 三、客户端1. 下载2. 设置java代理3. idea配置3.1 环境变量3.2 JVM参数3.3 启动日志 4. 启用网关插件 四、链路…

C++和OpenGL实现3D游戏编程【目录】

欢迎来到zhooyu的专栏。 个人主页&#xff1a;【zhooyu】 文章专栏&#xff1a;【OpenGL实现3D游戏编程】 贝塞尔曲面演示&#xff1a; 贝塞尔曲面演示zhooyu 本专栏内容&#xff1a; 我们从游戏的角度出发&#xff0c;用C去了解一下游戏中的功能都是怎么实现的。这一切还是要…

电脑ip会因为换了网络改变吗

在当今数字化时代&#xff0c;IP地址作为网络世界中的“门牌号”&#xff0c;扮演着至关重要的角色。它不仅是设备在网络中的唯一标识&#xff0c;也是数据交换和信息传递的基础。然而&#xff0c;对于普通用户而言&#xff0c;一个常见的问题便是&#xff1a;当电脑连接到不同…