leetcode判断子序列

news/2024/5/25 9:46:41/文章来源:https://blog.csdn.net/buptlzl/article/details/136713686

在这里插入图片描述
本题中,我们可以删除原始字符串的一些字符但是不能改变其他字符的位置,这种求子序列的题都可以用动态规划来解决。
首先我们要确定dp数组的定义,这里我们将dp数组定义为dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]。

然后我们确定递推公式,这里,
if (s[i - 1] == t[j - 1])
t中找到了一个字符在s中也出现了
if (s[i - 1] != t[j - 1])
相当于t要删除元素,继续匹配

if (s[i - 1] == t[j - 1]),那么dp[i][j] = dp[i - 1][j - 1] + 1;,因为找到了一个相同的字符,相同子序列长度自然要在dp[i-1][j-1]的基础上加1(如果不理解,在回看一下dp[i][j]的定义)

if (s[i - 1] != t[j - 1]),此时相当于t要删除元素,t如果把当前元素t[j - 1]删除,那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]的比较结果了,即:dp[i][j] = dp[i][j - 1];

初始化,无论那个字符串为空,其匹配长度肯定都是0;

class Solution {public boolean isSubsequence(String s, String t) {int length1 = s.length(); int length2 = t.length();int[][] dp = new int[length1+1][length2+1];for(int i = 1; i <= length1; i++){for(int j = 1; j <= length2; j++){if(s.charAt(i-1) == t.charAt(j-1)){dp[i][j] = dp[i-1][j-1] + 1;}else{dp[i][j] = dp[i][j-1];}}}if(dp[length1][length2] == length1){return true;}else{return false;}}
}

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

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

相关文章

29-Java组合实体模式 (Composite Entity Pattern)

Java组合实体模式 实现范例 组合实体模式&#xff08;Composite Entity Pattern&#xff09;用在 EJB 持久化机制中一个组合实体是一个 EJB 实体 bean&#xff0c;代表了对象的图解当更新一个组合实体时&#xff0c;内部依赖对象 beans 会自动更新&#xff0c;因为它们是由 EJB…

vscode的 c++ 环境搭建

2024.3.11 一、vscode的安装 Visual Studio Code - Code Editing. Redefinedhttps://code.visualstudio.com/#alt-downloads点击下载即可 &#xff08;普通的软件安装&#xff0c;这里跳过&#xff09; 安装完后&#xff0c;下载 C/C 和 C/C Extension Pack 两个模块 二、 M…

UI自动化、性能、API测试一体平台:RunnerGo

UI自动化测试已经成为现代软件开发过程中不可或缺的一部分。它能够提供诸多优势&#xff0c;包括提高测试效率、减少人力成本、提升软件质量等。同时&#xff0c;可视化工具为UI自动化测试带来了更多便利和灵活性。RunnerGo近期上线脚本录制器&#xff0c;根据你的测试操作直接…

【数据分析】数据分析介绍

专栏文章索引&#xff1a;【数据分析】专栏文章索引 目录 一、介绍 二、生活中的数据分析 1.无处不在的数据 2.为什么要进行数据分析&#xff1f; 三、数据挖掘案例 1.案例分析 一、介绍 数据采集&#xff1a;数据采集是指从不同来源收集原始数据的过程&#xff0c;包括…

基于jsp+mysql+Spring+mybatis的SSM汽车保险理赔管理系统设计和实现

基于jspmysqlSpringmybatis的SSM汽车保险理赔管理系统设计和实现 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐…

产品必会的30个Axure使用技巧

1. 安装Axure后要做的第一件事 如果系统崩溃后&#xff0c;再次进入时&#xff0c;系统一般会提示恢复最近备份的文件。也可以通过文件→从“备份中恢复”找回最新的版本。 2. 必须会的快捷键 快捷键不需要刻意去记忆&#xff0c;经常使用就熟记于心 3. 日常技巧汇总 &#…

【Stable Diffusion】入门-03:图生图基本步骤+参数解读

目录 1 图生图原理2 基本步骤2.1 导入图片2.2 书写提示词2.3 参数调整 3 随机种子的含义4 拓展应用 1 图生图原理 当提示词不足以表达你的想法&#xff0c;或者你希望以一个更为简单清晰的方式传递一些要求的时候&#xff0c;可以给AI输入一张图片&#xff0c;此时图片和文字是…

rust学习(简单链表)

编写一个简单链表&#xff0c;主要遇到的问题就是next指针&#xff08;按照C的写法&#xff09;的数据如何定义。按照网上的建议&#xff0c;一般定义如下&#xff1a; struct Node {pub value:u32,pub next:Option<Rc<RefCell<Node>>>, //1 }1.用Option主要…

CSS 文档流

是指页面上的元素在摆放的时候所占用的空间&#xff0c;也泛指页面元素放置的位置。 块元素&#xff1a;比如li标签或者h1这种&#xff0c;都是默认自上而下摆放的。内联标签&#xff1a;如果是span标签或者strong标签&#xff0c;它是从左到右进行摆放的。 有些场景并非得从…

HTML 学习笔记(十)块和内联

每个HTML元素都有一个默认的显示值&#xff0c;显示值又可以再分为block(块)和inline(内联) 一、块元素 通过F12进入浏览器开发者模式查看该元素会发现其所占宽度为整个网页的宽度 1.div标签 通过div标签将一些元素装进"盒子"&#xff0c;从而对盒子中的全部元素…

mysql5.6---windows和linux安装教程和忘记密码怎么办

一、windows安装 1.完成解压 解压完成之后将其放到你喜欢的地址当中去&#xff0c;这里我默认放在了D盘&#xff0c;这是我的根目录 2.配置环境变量 我的电脑->属性->高级->环境变量->系统变量 选择PATH,在其后面添加: (注意自己的安装地址) D:\mysql-5.6.49…

产品必会的6个Axure使用技巧(高阶)

1. 事件也可以复制/剪切/粘贴 只需要选中事件&#xff0c;复制/剪切&#xff0c;再选择其它事件&#xff0c;即可粘贴到这个事件上。同时支持跨页面的复制粘贴。 2. Axure支持复制粘贴Excel里的表格 具体操作 在excel里复制具体内容&#xff0c;如下图&#xff1a; 进入axur…

phpcms上传导致getshell详解及案例

一、环境 这里我根据大佬的文章将环境复原 phpcms上传导致getshell详解及案例 | 离别歌 回忆phpcms头像上传漏洞以及后续影响 | 离别歌 二、代码&#xff1a; php&#xff1a; <?php header("Content-Type:text/html; charsetutf-8"); require_once(pclzip…

交叉注意力融合时域、频域特征的FFT + CNN -BiLSTM-CrossAttention电能质量扰动识别模型

往期精彩内容&#xff1a; 电能质量扰动信号数据介绍与分类-Python实现-CSDN博客 Python电能质量扰动信号分类(一)基于LSTM模型的一维信号分类-CSDN博客 Python电能质量扰动信号分类(二)基于CNN模型的一维信号分类-CSDN博客 Python电能质量扰动信号分类(三)基于Transformer…

深入理解 CSS——CSS进阶与实践(5w字高频面试题整理)

本文总结了CSS高频面试题&#xff0c;并搭配了演示动画进行CSS样式演示。介绍了关于如何理解盒模型&#xff0c;如何实现块级元素水平居中&#xff0c;如何实现两侧固定中间自适应的三栏布局、如何实现两栏布局&#xff0c;如何进行响应式设计&#xff0c;对BFC的理解&#xff…

【计算机网络】概述 习题

体系结构 练习题 体系结构 真题 时延相关习题 参考公式&#xff1a; 习题1 题解&#xff1a; 发送时延1b 然后通过传播时延传到对面。即1b的发送时延剩下的传播时延 习题1扩展&#xff1a; 将距离修改为20米&#xff0c;其他条件不变。 将距离修改为10米&#xff0c;其他条…

PostgreSQL从入门到精通教程 - 第47讲:JMETER工具使用

PostgreSQL从小白到专家&#xff0c;是从入门逐渐能力提升的一个系列教程&#xff0c;内容包括对PG基础的认知、包括安装使用、包括角色权限、包括维护管理、、等内容&#xff0c;希望对热爱PG、学习PG的同学们有帮助&#xff0c;欢迎持续关注CUUG PG技术大讲堂。 第47讲&…

安装kibaba

官方地址&#xff1a;Past Releases of Elastic Stack Software | Elastic 直接下载就可以 安装好了之后开始配置文件/kibana/config打开kibanba.yml server.port:5601 服务器地址 sercer.name:kibana 服务器名称 kibana.index:.kibana 索引 elasticsearch.hosts:[http://1…

鸿蒙Harmony应用开发—ArkTS声明式开发(基础手势:TextArea)

多行文本输入框组件&#xff0c;当输入的文本内容超过组件宽度时会自动换行显示。 高度未设置时&#xff0c;组件无默认高度&#xff0c;自适应内容高度。宽度未设置时&#xff0c;默认撑满最大宽度。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&…

加密货币在网络违法犯罪活动中的利用情况调查

一、调查背景 区块链基于分布式共识和经济激励等手段&#xff0c;在开放式、无许可的网络空间中&#xff0c;为价值的确立、存储、转移提供了新的解决方案。然而随着加密生态在过去若干年的快速发展&#xff0c;加密货币也越来越多地被用于各类风险活动&#xff0c;为网络赌博…