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

【多维动态规划】Leetcode 97. 交错字符串【中等】

交错字符串

给定三个字符串 s1、s2、s3,请你帮忙验证 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

解题思路

定义一个二维布尔数组 dp,其中 dp[i][j] 表示 s3 的前 i + j 个字符是否可以由s1 的前 i 个字符和 s2 的前 j 个字符交错组成。具体的递推关系如下:

初始条件:

  • dp[0][0] = true,表示两个空字符串可以组成空字符串。

递推关系:

  • 如果 dp[i-1][j] 为真且 s1[i-1] == s3[i + j - 1],则 dp[i][j] = true。
    dp[i-1][j] 表示 s3 的前 i + j - 1 个字符可以通过 s1 的前 i-1 个字符和 s2 的前 j 个字符交错组成。
    如果 s1 的第 i 个字符 s1[i-1] 等于 s3 的第 i + j 个字符 s3[i + j - 1],
    则可以在 s3 的前 i + j - 1 个字符的基础上加上 s1 的第 i 个字符组成 s3 的前 i + j 个字符。
    因此,dp[i][j] = true。

  • 同理,如果 dp[i][j-1] 为真且 s2[j-1] == s3[i + j - 1],则 dp[i][j] = true。

最终结果:

  • dp[s1.length()][s2.length()] 表示 s3 是否可以由 s1 和 s2 交错组成。

Java实现

public class InterleavingString {public boolean isInterleave(String s1, String s2, String s3) {int m = s1.length();int n = s2.length();if (m + n != s3.length()) {return false;}boolean[][] dp = new boolean[m + 1][n + 1];dp[0][0] = true;// 初始化第一列for (int i = 1; i <= m; i++) {dp[i][0] = dp[i-1][0] && s1.charAt(i-1) == s3.charAt(i-1);}// 初始化第一行for (int j = 1; j <= n; j++) {dp[0][j] = dp[0][j-1] && s2.charAt(j-1) == s3.charAt(j-1);}// 填充 dp 表for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {dp[i][j] = (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i + j - 1)) || (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i + j - 1));}}return dp[m][n];}// 测试用例public static void main(String[] args) {InterleavingString solution = new InterleavingString();System.out.println(solution.isInterleave("aabcc", "dbbca", "aadbbcbcac"));  // 期望输出: trueSystem.out.println(solution.isInterleave("aabcc", "dbbca", "aadbbbaccc"));  // 期望输出: false}
}

时间空间复杂度

  • 时间复杂度:O(m * n),其中 m 是 s1 的长度,n 是 s2 的长度,需要遍历整个 dp 数组。
  • 空间复杂度:O(m * n),需要一个二维数组 dp 存储中间结果。

相关文章:

【多维动态规划】Leetcode 97. 交错字符串【中等】

交错字符串 给定三个字符串 s1、s2、s3&#xff0c;请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。 两个字符串 s 和 t 交错 的定义与过程如下&#xff0c;其中每个字符串都会被分割成若干 非空 子字符串 子字符串 是字符串中连续的 非空 字符序列。 s s1 s2 … snt…...

【JavaScript脚本宇宙】精通前端开发:六大热门CSS框架详解

前端开发的利器&#xff1a;深入了解六大CSS框架 前言 在现代Web开发中&#xff0c;选择适合的前端框架和工具包是构建高效、响应式和美观的网站或应用程序的关键。本文将详细介绍六个广受欢迎的CSS框架&#xff1a;Bootstrap、Bulma、Tailwind CSS、Foundation、Materialize…...

开发技术-Java集合(List)删除元素的几种方式

文章目录 1. 错误的删除2. 正确的方法2.1 倒叙删除2.2 迭代器删除2.3 removeAll() 删除2.4 removeIf() 最简单的删除 3. 总结 1. 错误的删除 在写代码时&#xff0c;想将其中的一个元素删除&#xff0c;就遍历了 list &#xff0c;使用了 remove()&#xff0c;发现效果并不是想…...

c++ 递归

递归函数是指在函数定义中调用自身的函数。C语言也支持递归函数。 下面是一个使用递归函数计算阶乘的例子&#xff1a; #include <iostream> using namespace std;int factorial(int n) {// 基本情况&#xff0c;当 n 等于 0 或 1 时&#xff0c;阶乘为 1if (n 0 || n…...

RedHat9 | podman容器

1、容器技术介绍 传统问题 应用程序和依赖需要一起安装在物理主机或虚拟机上的操作系统应用程序版本比当前操作系统安装的版本更低或更新两个应用程序可能需要某一软件的不同版本&#xff0c;彼此版本之间不兼容 解决方式 将应用程序打包并部署为容器容器是与系统的其他部分…...

边缘计算项目有哪些

边缘计算项目在多个领域得到了广泛的应用&#xff0c;以下是一些典型的边缘计算项目案例&#xff1a; 1. **智能交通系统**&#xff1a;通过在交通信号灯、监控摄像头等设备上部署边缘计算&#xff0c;可以实时分析交通流量&#xff0c;优化交通信号控制&#xff0c;减少拥堵&…...

计算fibonacci数列每一项时所需的递归调用次数

斐波那契数列是一个经典的数列&#xff0c;其中每一项是前两项的和&#xff0c;定义为&#xff1a; [ F(n) F(n-1) F(n-2) ] 其中&#xff0c;( F(0) 0 ) 和 ( F(1) 1 )。 对于计算斐波那契数列的第 ( n ) 项&#xff0c;如果使用简单的递归方法&#xff0c;其时间复杂度是…...

【教学类65-05】20240627秘密花园涂色书(中四班练习)

【教学类65-03】20240622秘密花园涂色书03&#xff08;通义万相&#xff09;&#xff08;A4横版1张&#xff0c;一大 68张纸136份&#xff09;-CSDN博客 背景需求: 打印以下几款秘密花园样式&#xff08;每款10份&#xff09;给中四班孩子玩一下&#xff0c;看看效果 【教学类…...

Python 学习之基础语法(一)

Python的语法基础主要包括以下几个方面&#xff0c;下面将逐一进行分点表示和归纳&#xff1a; 一、基本语法 1. 注释 a. 单行注释&#xff1a;使用#开头&#xff0c;例如# 这是一个单行注释。 b. 多行注释&#xff1a;使用三引号&#xff08;可以是三个单引号或三个双引号&…...

日志分析-windows系统日志分析

日志分析-windows系统日志分析 使用事件查看器分析Windows系统日志 cmd命令 eventvwr 筛选 清除日志、注销并重新登陆&#xff0c;查看日志情况 Windows7和Windowserver2008R2的主机日志保存在C:\Windows\System32\winevt\Logs文件夹下&#xff0c;Security.evtx即为W…...

【ARM】MDK工程切换高版本的编译器后出现error A1137E报错

【更多软件使用问题请点击亿道电子官方网站】 1、 文档目标 解决工程从Compiler 5切换到Compiler 6进行编译时出现一些非语法问题上的报错。 2、 问题场景 对于一些使用Compiler 5进行编译的工程&#xff0c;要切换到Compiler 6进行编译的时候&#xff0c;原本无任何报错警告…...

深入 SSH:解锁本地转发、远程转发和动态转发的潜力

文章目录 前言一、解锁内部服务&#xff1a;SSH 本地转发1.1 什么是 SSH 本地转发1.2 本地转发应用场景 二、打开外部访问大门&#xff1a;SSH 远程转发2.1 什么是 SSH 远程转发2.2 远程转发应用场景 三、动态转发&#xff1a;SSH 让你拥有自己的 VPN3.1 什么是 SSH 动态转发3.…...

python如何把一个函数的返回值,当成这个函数的参数值

python如何把一个函数的返回值&#xff0c;当成这个函数的参数值 1. 递归调用 递归是一种函数自己调用自己的方法。在递归调用中&#xff0c;你可以将前一次调用的返回值作为下一次调用的参数。 def recursive_function(x):# 函数逻辑if 条件满足:return 结果else:return rec…...

【融合ChatGPT等AI模型】Python-GEE遥感云大数据分析、管理与可视化及多领域案例应用

随着航空、航天、近地空间遥感平台的持续发展&#xff0c;遥感技术近年来取得显著进步。遥感数据的空间、时间、光谱分辨率及数据量均大幅提升&#xff0c;呈现出大数据特征。这为相关研究带来了新机遇&#xff0c;但同时也带来巨大挑战。传统的工作站和服务器已无法满足大区域…...

SpringBoot: Eureka入门

1. IP列表 公司发展到一定的规模之后&#xff0c;应用拆分是无可避免的。假设我们有2个服务(服务A、服务B)&#xff0c;如果服务A要调用服务B&#xff0c;我们能怎么做呢&#xff1f;最简单的方法是让服务A配置服务B的所有节点的IP&#xff0c;在服务A内部做负载均衡调用服务B…...

Typescript 【实用教程】(2024最新版)含类型声明,类型断言,函数,接口,泛型等

简介 TypeScript 是 JavaScript 的超集&#xff0c;是 JavaScript&#xff08;弱类型语言&#xff09; 的强类型版本。 拥有类型机制文件后缀 .tsTypescript type ES6TypeScript 和 JavaScript 的关系类似 less 和 css 的关系TypeScript对 JavaScript 添加了一些扩展&#x…...

智慧校园-实训管理系统总体概述

智慧校园实训管理系统&#xff0c;专为满足高等教育与职业教育的特定需求而设计&#xff0c;它代表了实训课程管理领域的一次数字化飞跃。此系统旨在通过革新实训的组织结构、执行流程及评估标准&#xff0c;来增强学生的实践操作技能和教师的授课效率&#xff0c;为社会输送具…...

如何用GPT开发一个基于 GPT 的应用?

原文发自博客&#xff1a;GPT应用开发小记 如何开发一个基于 GPT 的应用&#xff1f;答案就在问题里&#xff0c;那就是用 GPT 来开发基于 GPT 的应用。本文以笔者的一个开源项目 myGPTReader 为例&#xff0c;分享我是如何基于 GPT 去开发这个系统的&#xff0c;这个系统的功能…...

大数据生态体系中各组件的区别面试题(更新)

一、MapReduce与Spark有什么区别&#xff1f; 1、处理方式: MapReduce基于磁盘处理数据&#xff0c;将中间结果保存到磁盘中,减少了内存占用&#xff0c;计算速度慢。 基于内存处理数据&#xff0c;将计算的中间结果保存到内存中&#xff0c;计算速度快。2、资源申请方式&…...

数字信号处理实验一(离散信号及离散系统的MATLAB编程实现)

实验要求&#xff1a; 离散信号及离散系统的MATLAB编程实现&#xff08;2学时&#xff09; 要求&#xff1a; 编写一程序&#xff0c;输出一定长度&#xff08;点数&#xff09;&#xff0c;具有一定幅度、&#xff08;角&#xff09;频率和初始相位的实&#xff08;或复&…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

大数据零基础学习day1之环境准备和大数据初步理解

学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 &#xff08;1&#xff09;设置网关 打开VMware虚拟机&#xff0c;点击编辑…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

Swagger和OpenApi的前世今生

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

docker 部署发现spring.profiles.active 问题

报错&#xff1a; org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...

#Uniapp篇:chrome调试unapp适配

chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器&#xff1a;Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...