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

【Leetcode-面试经典150题-day22】

目录

97. 交错字符串


 

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 连接。

【输入样例】s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"

【输出样例】true

解题思路:

1. 如果s1的长度+s2的长度不等于s3的长度,直接返回false,否则

2. 定义动态数组dp[i][j]表示s1的前i个元素和s2的第j个元素能够否交错组成s3的前i+j个元素;

3. dp[i][j]能否为true,取决于dp[i-1][j]是否为true&&s1[i]==s3[i+j],同理dp[i][j]也取决于dp[i][j-1]&&s2[j]==s3[i+j];

4. dp的边界条件应该是dp[0][0]=true,即s1和s2的前0个元素可以构成s3的前0个元素(都为空)。

class Solution {public boolean isInterleave(String s1, String s2, String s3) {//先判断长度int len1 = s1.length();int len2 = s2.length();int len3 = s3.length();if(len3 != len1+len2){return false;}boolean[][] dp = new boolean[len1+1][len2+1];dp[0][0] = true;for(int i = 0; i <= len1; ++i){for(int j = 0; j <= len2; ++j){int p = i + j - 1;if(i > 0){dp[i][j] = dp[i][j] || (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(p));}if(j > 0){dp[i][j] = dp[i][j] || (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(p));}}}return dp[len1][len2];}
}

时间: 击败了66.74%

内存: 击败了25.11% 

相关文章:

【Leetcode-面试经典150题-day22】

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

LDAP服务器如何重启

1、find / -name ldap 该命令只会从根路径下查看ldap文件夹 find / -name ldap2、该命令会从根路径/查看所有包含ldap路径的文件夹&#xff0c;会查询出所有&#xff0c;相当于全局查询 find / -name *ldap*2、启动OpenLADP 找到LDAP安装目录后&#xff0c;执行以下命令 #直…...

AP51656 LED车灯电源驱动IC 兼容替代PT4115 PT4205 PWM和线性调光

产品描述 AP51656是一款连续电感电流导通模式的降压恒流源 用于驱动一颗或多颗串联LED 输入电压范围从 5V 到 60V&#xff0c;输出电流 可达 1.5A 。根据不同的输入电压和 外部器件&#xff0c; 可以驱动高达数十瓦的 LED。 内置功率开关&#xff0c;采用高端电流采样设置 …...

浅析安防视频监控平台EasyCVR视频融合平台接入大量设备后是如何维持负载均衡的

安防视频监控平台EasyCVR视频融合平台可拓展性强、视频能力灵活、部署轻快&#xff0c;可支持的主流标准协议有国标GB28181、RTSP/Onvif、RTMP等&#xff0c;以及支持厂家私有协议与SDK接入&#xff0c;包括海康Ehome、海大宇等设备的SDK等。视频汇聚融合管理平台EasyCVR既具备…...

SIEM 中不同类型日志监控及分析

安全信息和事件管理&#xff08;SIEM&#xff09;解决方案通过监控来自网络的不同类型的数据来确保组织网络的健康安全状况&#xff0c;日志数据记录设备上发生的每个活动以及整个网络中的应用程序&#xff0c;若要评估网络的安全状况&#xff0c;SIEM 解决方案必须收集和分析不…...

【java基础复习】java中的数组在内存中是如何存储的?

基本数据类型与内存存储数组类型与内存存储为什么数组需要两块空间&#xff1f;感谢 &#x1f496; 基本数据类型与内存存储 首先&#xff0c;让我们回顾一下基本数据类型的内存存储方式。对于一个基本类型变量&#xff0c;例如int类型的变量a&#xff0c;内存中只有一块内存空…...

MySQL数据库 MHA高可用

MySQL MHA 什么是 MHA MHA&#xff08;MasterHigh Availability&#xff09;是一套优秀的MySQL高可用环境下故障切换和主从复制的软件。 MHA 的出现就是解决MySQL 单点的问题。 MySQL故障切换过程中&#xff0c;MHA能做到0-30秒内自动完成故障切换操作。 MHA能在故障切换的…...

leetcode669. 修剪二叉搜索树(java)

修剪二叉搜索树 题目描述递归代码演示&#xff1a; 题目描述 难度 - 中等 LC - 669. 修剪二叉搜索树 给你二叉搜索树的根节点 root &#xff0c;同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树&#xff0c;使得所有节点的值在[low, high]中。修剪树 不应该 改变保留…...

计算机网络的故事——确认访问用户身份的认证

确认访问用户身份的认证 HTTP使用的认证方式&#xff1a;BASIC认证&#xff08;基本认证&#xff09;、DIGEST&#xff08;摘要认证&#xff09;、SSL客户端认证、FormBase认证&#xff08;基于表单认证&#xff09;。 基于表单的认证&#xff1a;涉及到session管理以及cookie…...

C#禁用或启用任务管理器

参考文档https://zhuanlan.zhihu.com/p/95156063 借助上述参考文档里的C#操作注册表类&#xff0c;禁用或启用任务管理器 using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace HideTaskMgr { class Program { …...

【Redis】NoSQL之Redis的配置及优化

关系数据库与非关系数据库 关系型数据库 关系型数据库是一个结构化的数据库&#xff0c;创建在关系模型&#xff08;二维表格模型&#xff09;基础上&#xff0c;一般面向于记录。 SQL 语句&#xff08;标准数据查询语言&#xff09;就是一种基于关系型数据库的语言&a…...

【数据库】如何利用Python中的petl将PostgreSQL中所有表的外键删除,迁移数据,再重建外键

一、简介 在数据库管理中&#xff0c;外键是一种重要的约束&#xff0c;用于确保数据的一致性和完整性。然而&#xff0c;在某些情况下&#xff0c;我们可能需要删除或修改外键。本文将介绍如何使用Python中的petl库将PostgreSQL中所有表的外键删除&#xff0c;迁移数据&#…...

Si24R2F+畜牧 耳标测体温开发资料

Si24R2F是针对IOT应用领域推出的新款超低功耗2.4G内置NVM单发射芯片。广泛应用于2.4G有源活体动物耳标&#xff0c;带实时测温计步功能。相较于Si24R2E&#xff0c;Si24R2F增加了温度监控、自动唤醒间隔功能&#xff1b;发射功率由7dBm增加到12dBm&#xff0c;距离更远&#xf…...

阿里云服务器退款流程_退订入口_到账时间说明

阿里云服务器如何退款&#xff1f;云服务器在哪申请退款&#xff1f;在用户中心订单管理中的退订管理中退款&#xff0c;阿里云百科分享阿里云服务器退款流程&#xff0c;包括申请退款入口、云服务器退款限制条件、退款多久到账等详细说明&#xff1a; 目录 阿里云服务器退款…...

自然语言处理实战项目17-基于多种NLP模型的诈骗电话识别方法研究与应用实战

大家好&#xff0c;我是微学AI&#xff0c;今天给大家介绍一下自然语言处理实战项目17-基于NLP模型的诈骗电话识别方法研究与应用&#xff0c;相信最近小伙伴都都看过《孤注一掷》这部写实的诈骗电影吧&#xff0c;电影主要围绕跨境网络诈骗展开&#xff0c;电影取材自上万起真…...

安全错误攻击

近年来基于错误的密码分析&#xff08;fault-based cryptanalysis&#xff09;已成为检测智能卡&#xff08;Smartcard&#xff09;安全的重要因素。这种基于错误的密码分析&#xff0c;假设攻击者可以向智能卡中导入一定数量的、某种类型的错误&#xff0c;那么智能卡会输出错…...

ELK安装、部署、调试 (八)logstash配置语法详解

input {#输入插件 }filter {#过滤插件 }output {#输出插件 } 1.读取文件。 使用filewatch的ruby gem库来监听文件变化&#xff0c;并通过.sincedb的数据库文件记录被监听日志we年的读取进度&#xff08;时间 搓&#xff09; 。sincedb数据文件的默认路径为<path.data>/…...

SPI协议

文章目录 前言一、简介1、通信模式2、总线定义3、SPI通信结构4、SPI通讯时序5、SPI数据交互过程 二、多从机模式1、多NSS2、菊花链3、SPI通信优缺点4、UART、IIC、SPI 区别 三、总结四、参考资料 前言 SPI协议是我们的重要通信协议之一&#xff0c;我们需要掌握牢靠。 一、简介…...

机器学习算法系列————决策树(二)

1.什么是决策树 用于解决分类问题的一种算法。 左边是属性&#xff0c;右边是标签。 属性选择时用什么度量&#xff0c;分别是信息熵和基尼系数。 这里能够做出来特征的区分。 下图为基尼系数为例进行计算。 下面两张图是对婚姻和年收入的详细计算过程&#xff08;为GINI系…...

ACM中的数论

ACM中的数论是计算机科学领域中的一个重要分支&#xff0c;它主要研究整数的性质、运算规律和它们之间的关系。在ACM竞赛中&#xff0c;数论问题经常出现&#xff0c;因此掌握一定的数论知识对于参加ACM竞赛的选手来说是非常重要的。本文将介绍一些常见的数论概念和方法&#x…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级

在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...