【LeetCode】392. 判断子序列(简单)——代码随想录算法训练营Day54
题目链接:392. 判断子序列
题目描述
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
进阶:
如果有大量输入的 S,称作 S1, S2, ... , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?
示例 1:
输入:s = "abc", t = "ahbgdc" 输出:true
示例 2:
输入:s = "axc", t = "ahbgdc" 输出:false
提示:
0 <= s.length <= 1000 <= t.length <= 10^4- 两个字符串都只由小写字符组成。
文章讲解:代码随想录
视频讲解:动态规划,用相似思路解决复杂问题 | LeetCode:392.判断子序列_哔哩哔哩_bilibili
题解1:动态规划
思路:使用动态规划法求解子序列问题,本题判断 s 和 t 的最长公共子序列长度是否为 s 的长度。
动态规划分析:
- dp 数组以及下标的含义:dp[i][j] 表示以 s[i] 结尾和 t[j] 结尾的最长公共子序列长度。
- 递推公式:当 s[i - 1] 等于 t[j - 1] 时,dp[i][j] = dp[i - 1][j - 1] + 1;否则,dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])。
- dp 数组初始化:全部初始化为0。
- 遍历顺序:从上往下,从左往右。
- 打印 dp 数组:以输入 s = "abc"、t = "ahbgdc" 为例,dp 数组为 [ [ 0, 0, 0, 0, 0, 0, 0 ], [ 0, 1, 1, 1, 1, 1, 1 ], [ 0, 1, 1, 2, 2, 2, 2 ], [ 0, 1, 1, 2, 2, 2, 3 ] ]。
/*** @param {string} s* @param {string} t* @return {boolean}*/
var isSubsequence = function(s, t) {const dp = new Array(s.length + 1).fill().map(() => new Array(t.length + 1).fill(0));for (let i = 1; i <= s.length; i++) {for (let j = 1; j <= t.length; j++) {if (s[i - 1] === t[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[s.length][t.length] === s.length;
};
分析:时间复杂度为 O(m * n),空间复杂度为 O(m * n)。
题解2:双指针
思路:
/*** @param {string} s* @param {string} t* @return {boolean}*/
var isSubsequence = function(s, t) {let index = 0;for (let i = 0; i < t.length; i++) {if (t[i] === s[index]) {index++;}}return index === s.length;
};
分析:时间复杂度为 O(n),空间复杂度为 O(1)。
收获
练习使用动态规划法求解子序列问题。
相关文章:
【LeetCode】392. 判断子序列(简单)——代码随想录算法训练营Day54
题目链接:392. 判断子序列 题目描述 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"…...
1. Typescript入门
TS 基础 Typescript 在线编译平台 基础类型 boolean、number 和 string 类型 boolean let isHandsome: boolean true赋值与定义的不一致,会报错,静态类型语言的优势就体现出来了,可以帮助我们提前发现代码中的错误。 let isHandsome: …...
【Git】merge时报错:refusing to merge unrelated histories
文章目录 一、问题二、解决办法1、将feature分支的东西追加到master分支中2、将feature里的东西直接覆盖到master分支中 一、问题 今天将feature分支合并到master时报错:refusing to merge unrelated histories(拒绝合并无关历史) 报错原因&…...
树状数组+离散化求逆序对超详细讲解!
树状数组离散化求逆序对 用一个数组 w [ ] w[] w[]来记录遍历到当前数时,每个数出现的次数 由于只关心每个数前边有多少个数比他大,遍历到 i i i时,求大于 a [ i ] a[i] a[i]的数有多少个,就是对 [ a [ i ] , n ] [a[i], n] [a[i…...
《解密云计算:企业之选》
前言 在当今数字化时代,企业面临着巨大的数据处理压力和信息化需求,传统的IT架构已经无法满足日益增长的业务需求。在这样的背景下,越来越多的企业开始转向云计算,以实现灵活、高效和可扩展的IT资源管理和利用。 云计算 云计算是…...
地址分词 | EXCEL批量进行地址分词,标准化为十一级地址
一 需求 物流需要对用户输入地址进行检查,受用户录入习惯地址可能存在多种问题。 地址标准化是基于地址引擎和地址大数据模型,自动将地址信息标准化为省、市、区市县、街镇、小区、楼栋、单元、楼层、房屋、房间等元素,补充层级缺失数据、构建…...
KubeSphere平台安装系列之二【Linux单节点部署KubeSphere】(2/3)
**《KubeSphere平台安装系列》** 【Kubernetes上安装KubeSphere(亲测–实操完整版)】(1/3) 【Linux单节点部署KubeSphere】(2/3) 【Linux多节点部署KubeSphere】(3/3) **《KubeS…...
网络安全: Kali Linux 使用 docker-compose 部署 openvas
目录 一、实验 1.环境 2.Kali Linux 安装docker与docker-compose 3.Kali Linux 使用docker-compose方式部署 openvas 4. KaliLinux 使用openvas 二、问题 1. 信息安全漏洞库 2.信息安全漏洞共享平台 3.Windows 更新指南与查询 4.CVE 查询 5.docker-compose 如何修改o…...
【学习考试心得】在誉天学习考试RHCE9.0的体验
作为华中第一位参加RHCE9.0线上考试的考生,很荣幸能来写这个心得,和大家分享一下线上的考试的一些体验。 一、学习体验 首先在红帽课程的学习中,跟着杨峰老师的脚步,整个学习过程中都非常有意思。杨峰老师充满磁性的声音和小王老师…...
Flip Clock(not good)
最近体验了一下iOS的翻页时钟app,很想自己做一个,但是效果不好 public class main {public static void main(String[] args) {//psvmnew MyFrame();} }import javax.swing.*; import java.awt.*; import java.io.File; import java.io.IOException; im…...
目标检测——摩托车头盔检测数据集
一、简介 首先,摩托车作为一种交通工具,具有高速、开放和稳定性差的特点,其事故发生率高,伤亡率排在机动车辆损伤的首位。因此,摩托车乘员头盔对于保护驾乘人员头部安全至关重要。在驾乘突发状况、人体受冲击时&#…...
Windows 安装 Xinference
Windows 安装 Xinference 0. 引言1. 创建虚拟环境2. 安装 pytorch3. 安装 llama_cpp_python4. 安装 chatglm-cpp5. 安装 Xinference6. 设置 model 路径7. 启动 Xinference8. 查看 Cluster Information 0. 引言 Xorbits Inference(Xinference)是一个性能…...
静态时序分析:SDC约束命令set_case_analysis详解
相关阅读 静态时序分析https://blog.csdn.net/weixin_45791458/category_12567571.html?spm1001.2014.3001.5482 目录 指定值 指定端口/引脚列表 简单使用 set_case_analysis命令用于对电路进行特定模式的设定,例如对于一个工作在正常模式下的芯片,…...
C++ · 代码笔记4 ·继承与派生
目录 前言010继承与派生简单例程020多级继承030使用using关键词更改访问权限040隐藏050派生类与基类成员函数同名时不构成重载060使用多级继承展示成员变量在内存中的分布情况071派生类在函数头调用基类构造函数072构造函数调用顺序080构造函数与析构函数的调用顺序091多重继承…...
解决uni-app中使用webview键盘弹起遮挡input输入框问题
这个平平无奇的回答,可能是全网最靠谱的解决方案。 这里我用的是vue3 setup .vue文件的方式 <view> <web-view :fullscreen"false" :webview-styles"{top: statusBarHeight40,height:height,progress: {color: green,height:1px } }"…...
Java注解介绍
Java注解 注解介绍元注解RetentionTargetDocumentedInherited接口类测试结果 注解介绍 Java注解(Annotation)是一种元数据(Metadata)的形式,它可以被添加到Java代码中的类、方法、变量、参数等元素上,以提…...
万字详解,Java实现低配版线程池
文章目录 1.什么是线程池2.线程池的优势3.原理4.代码编写4.1 阻塞队列4.2 ThreadPool线程池4.3 Worker工作线程4.4 代码测试 5. 拒绝策略5.1 抽象Reject接口5.2 BlockingQueue新增tryPut方法5.3 修改ThreadPool的execute方法5.4 ThreadPool线程池构造函数修改5.5 拒绝策略实现1…...
挂耳式蓝牙耳机哪家的好用?购买耳机前必须了解的几大要点
随着健康意识的提升,越来越多的人开始热衷于运动。运动不仅能够增强体质,对于我们这些忙碌的上班族而言,它也是一种极佳的减压方式。经过一天的辛勤工作,能够在户外跑步,让汗水带走压力,实在是一种享受。在…...
CSS文本属性
CSS文本属性 1.文本颜色2.文本间距3. 文本修饰4 .文本缩进5.文本对齐_水平6.行高7. vertical-align 1.文本颜色 属性名:color作用:控制文字的颜色。可选值: 颜色名rgb或rgbaHEX或HEXA (十六进制)HSL或HSLA 开发中常用…...
MySQL篇—执行计划之覆盖索引Using index和条件过滤Using where介绍(第三篇,总共三篇)
☘️博主介绍☘️: ✨又是一天没白过,我是奈斯,DBA一名✨ ✌✌️擅长Oracle、MySQL、SQLserver、Linux,也在积极的扩展IT方向的其他知识面✌✌️ ❣️❣️❣️大佬们都喜欢静静的看文章,并且也会默默的点赞收藏加关注❣…...
从Kinect到iPhone LiDAR:深度图如何从‘玩具’变成分割算法的‘神助攻’?
从Kinect到iPhone LiDAR:深度传感技术如何重塑图像分割的边界 十年前,当微软Kinect首次将深度摄像头带入消费市场时,计算机视觉领域的研究者们既兴奋又沮丧。兴奋的是,我们终于能够以低廉的价格获取场景的深度信息;沮丧…...
python argon2
## 关于 Python 中的 Argon2:一个密码哈希的现代选择 如果你写过需要处理用户密码的代码,肯定知道不能把密码原文存进数据库。早年很多系统用 MD5 或 SHA-1 这类快速哈希算法,后来大家发现这不够安全——显卡能每秒算几十亿次哈希,…...
老照片模糊发黄?别让珍贵回忆蒙尘,三步教你“复活”旧时光
在每个家庭的抽屉深处,或许都珍藏着一本厚重的相册。翻开它,泛黄的相纸、模糊的笑脸,瞬间将我们拉回到那个没有智能手机、没有高清摄像的年代。这些照片承载着父母的青春、我们的童年,是无可替代的宝贵记忆。然而,时光…...
别再死记硬背了!用Python+NetworkX快速上手ER、BA、WS、NW四大经典网络模型
用Python实战四大经典网络模型:从代码到洞察 在数据科学和网络分析领域,理解复杂网络的结构特性是每个从业者的必修课。但传统教材往往陷入数学公式的泥沼,让初学者望而生畏。本文将用Python和NetworkX带你直击四大经典网络模型(E…...
拆解一块TFT-LCD屏幕:聊聊驱动板上那颗Power IC是怎么‘发电’的
拆解一块TFT-LCD屏幕:驱动板上那颗Power IC的电力魔法 站在电子爱好者的视角,拆解一块TFT-LCD屏幕总能带来意想不到的惊喜。当我们小心翼翼地剥离背光模组和偏光片,露出那块布满精密电路的PCB时,最引人注目的往往是那颗被众多电容…...
用MPX4115气压传感器和51单片机做个简易气压计(附完整代码与电路图)
从零构建基于MPX4115的智能气压监测系统:硬件连接、代码解析与实战调试 气压监测在气象观测、无人机高度控制、工业设备监控等领域有着广泛应用。今天我们将使用经典的51单片机(以STC89C52为例)和MPX4115气压传感器,打造一个具备实…...
推荐一些可以用于论文降重的软件:哪些降重软件可以同时降低查重率和AIGC疑似率?2026年爆款论文降重工具实测TOP5,实测超实用!
CSDN学术效能专栏 / 2026届高压盲审突围指南: 各位C站的科研党们,离最终审稿死线仅剩不到两周。近期我的私信不断被一个致命问题轰炸:“博主,求推荐一些可以用于论文降重的软件!我的查重率是过了,但被知网查…...
GESP2023年9月认证C++三级( 第一部分选择题(1-8))
🏰 第1题 App是什么?题目: 手机上安装的 App 通常指的是( )A. 操作系统 B. 应用软件 C. 通话设备 D. 都不对✅答案:B1、🌟故事时间你有一部手机📱,手机里有:微…...
为什么你的.NET AI服务无法突破200 QPS?揭秘JIT预编译+NativeAOT+TensorRT插件协同失效的3个隐性陷阱
第一章:为什么你的.NET AI服务无法突破200 QPS?揭秘JIT预编译NativeAOTTensorRT插件协同失效的3个隐性陷阱当.NET开发者将AI推理服务从Kestrel托管模型迁移至NativeAOT TensorRT加速路径时,常遭遇QPS卡死在180–200区间的现象——即使CPU利用…...
别再死磕毕业论文!Paperxie 智能写作:大四生的「论文通关秘籍」
paperxie-免费查重复率aigc检测/开题报告/毕业论文/智能排版/文献综述/期刊论文https://www.paperxie.cn/ai/dissertationhttps://www.paperxie.cn/ai/dissertation 大四下学期的关键词,一半是毕业旅行、散伙饭,另一半却是改到崩溃的论文初稿、导师的红色…...
