【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方向的其他知识面✌✌️ ❣️❣️❣️大佬们都喜欢静静的看文章,并且也会默默的点赞收藏加关注❣…...
QuickLook OfficeViewer插件技术实现深度解析:无Office环境下的文档预览终极指南
QuickLook OfficeViewer插件技术实现深度解析:无Office环境下的文档预览终极指南 【免费下载链接】QuickLook.Plugin.OfficeViewer Word, Excel, and PowerPoint plugin for QuickLook. 项目地址: https://gitcode.com/gh_mirrors/qu/QuickLook.Plugin.OfficeView…...
浙江大学毕业论文LaTeX模板:学术写作的终极效率工具
浙江大学毕业论文LaTeX模板:学术写作的终极效率工具 【免费下载链接】zjuthesis Zhejiang University Graduation Thesis LaTeX Template 项目地址: https://gitcode.com/gh_mirrors/zj/zjuthesis 在浙江大学学术写作的旅途中,你是否曾为论文格式…...
从‘差异集’到‘代换’:图解Prolog与类型推断中的‘合一’核心思想
从‘差异集’到‘代换’:图解Prolog与类型推断中的‘合一’核心思想 在计算机科学的抽象丛林里,有些思想像暗河般贯穿多个领域。当Prolog解释器回答"谁杀了罗宾"时,当Haskell编译器推断出map :: (a -> b) -> [a] -> [b]的…...
别再死记硬背了!用Fastjson 1.2.62处理JSON,这3个真实业务场景你肯定遇到过
Fastjson实战:3个高频业务场景深度解析 每次看到同事在手动拼接JSON字符串,或者用反射处理复杂嵌套结构时,我都忍不住想分享Fastjson这个利器。作为阿里巴巴开源的JSON处理库,Fastjson在性能上一直保持着领先优势,特别…...
Jinger独自勇闯Microsoft AI TourShanghai
研究生凌晨奔赴上海✨ 赴一场Microsoft AI Tour之约 收获一枚纪念冰箱贴 简餐也意外合口味🍜 最惊喜的是! 终于和鱼皮老师合影圆梦📸 打卡了上次错过的武康大楼 虽没抽到心仪大奖 但此行已是满满收获 两次赴沪皆是匆匆步履 却都藏着独一份的欢…...
MATLAB实现光束形态变换:高斯光束到平顶光束的转换及SLM相位分布计算
MATLAB实现高斯光束到平顶光束的转变 基于GS算法或者直接计算SLM相位分布。一、引言 在光学工程、激光技术等领域,光束整形是一项关键技术,其核心目标是将一种光束的振幅、相位分布转换为目标分布,以满足特定应用场景的需求。本文所介绍的代码…...
告别串口模式:在Ubuntu 22.04上为FTDI芯片启用MPSSE功能(D2XX驱动保姆级教程)
解锁FTDI芯片的隐藏潜能:Ubuntu 22.04下D2XX驱动深度配置指南 当你在Linux系统中使用FT232H或FT4232H这类FTDI芯片时,是否曾好奇过它们除了串口通信之外还能做什么?实际上,这些芯片内置了强大的MPSSE引擎,能够实现SPI、…...
鸣潮自动化工具ok-ww:5分钟搞定每日重复任务的终极解决方案
鸣潮自动化工具ok-ww:5分钟搞定每日重复任务的终极解决方案 【免费下载链接】ok-wuthering-waves 鸣潮 后台自动战斗 自动刷声骸 一键日常 Automation for Wuthering Waves 项目地址: https://gitcode.com/GitHub_Trending/ok/ok-wuthering-waves 你是否厌倦…...
Infra岗位技术栈大揭秘:收藏这份学习路径,成为大模型高手!
本文整理了Infra岗位招聘中常见的技术栈,涵盖编程基础、Transformer算法、分布式训练、推理优化、系统底层等多个方面。内容涉及PyTorch、C、CUDA、并行处理、MoE、量化部署、高性能网络通信、GPU集群调度等关键技术。对于想要在大模型领域深入发展的程序员和小白&a…...
告别C盘爆满!手把手教你将Android模拟器AVD文件夹迁移到D盘(附环境变量配置详解)
彻底解决Android模拟器C盘空间占用问题:AVD文件夹迁移与性能优化实战 当你在Android Studio中启动模拟器时,是否注意到C盘空间正在以惊人的速度减少?这个问题困扰着许多开发者——默认情况下,Android Virtual Device(A…...
