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

【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 <= 100
  • 0 <= 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

题目链接&#xff1a;392. 判断子序列 题目描述 给定字符串 s 和 t &#xff0c;判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些&#xff08;也可以不删除&#xff09;字符而不改变剩余字符相对位置形成的新字符串。&#xff08;例如&#xff0c;"…...

1. Typescript入门

TS 基础 Typescript 在线编译平台 基础类型 boolean、number 和 string 类型 boolean let isHandsome: boolean true赋值与定义的不一致&#xff0c;会报错&#xff0c;静态类型语言的优势就体现出来了&#xff0c;可以帮助我们提前发现代码中的错误。 let isHandsome: …...

【Git】merge时报错:refusing to merge unrelated histories

文章目录 一、问题二、解决办法1、将feature分支的东西追加到master分支中2、将feature里的东西直接覆盖到master分支中 一、问题 今天将feature分支合并到master时报错&#xff1a;refusing to merge unrelated histories&#xff08;拒绝合并无关历史&#xff09; 报错原因&…...

树状数组+离散化求逆序对超详细讲解!

树状数组离散化求逆序对 用一个数组 w [ ] w[] w[]来记录遍历到当前数时&#xff0c;每个数出现的次数 由于只关心每个数前边有多少个数比他大&#xff0c;遍历到 i i i时&#xff0c;求大于 a [ i ] a[i] a[i]的数有多少个&#xff0c;就是对 [ a [ i ] , n ] [a[i], n] [a[i…...

《解密云计算:企业之选》

前言 在当今数字化时代&#xff0c;企业面临着巨大的数据处理压力和信息化需求&#xff0c;传统的IT架构已经无法满足日益增长的业务需求。在这样的背景下&#xff0c;越来越多的企业开始转向云计算&#xff0c;以实现灵活、高效和可扩展的IT资源管理和利用。 云计算 云计算是…...

地址分词 | EXCEL批量进行地址分词,标准化为十一级地址

一 需求 物流需要对用户输入地址进行检查&#xff0c;受用户录入习惯地址可能存在多种问题。 地址标准化是基于地址引擎和地址大数据模型&#xff0c;自动将地址信息标准化为省、市、区市县、街镇、小区、楼栋、单元、楼层、房屋、房间等元素&#xff0c;补充层级缺失数据、构建…...

KubeSphere平台安装系列之二【Linux单节点部署KubeSphere】(2/3)

**《KubeSphere平台安装系列》** 【Kubernetes上安装KubeSphere&#xff08;亲测–实操完整版&#xff09;】&#xff08;1/3&#xff09; 【Linux单节点部署KubeSphere】&#xff08;2/3&#xff09; 【Linux多节点部署KubeSphere】&#xff08;3/3&#xff09; **《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线上考试的考生&#xff0c;很荣幸能来写这个心得&#xff0c;和大家分享一下线上的考试的一些体验。 一、学习体验 首先在红帽课程的学习中&#xff0c;跟着杨峰老师的脚步&#xff0c;整个学习过程中都非常有意思。杨峰老师充满磁性的声音和小王老师…...

Flip Clock(not good)

最近体验了一下iOS的翻页时钟app&#xff0c;很想自己做一个&#xff0c;但是效果不好 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…...

目标检测——摩托车头盔检测数据集

一、简介 首先&#xff0c;摩托车作为一种交通工具&#xff0c;具有高速、开放和稳定性差的特点&#xff0c;其事故发生率高&#xff0c;伤亡率排在机动车辆损伤的首位。因此&#xff0c;摩托车乘员头盔对于保护驾乘人员头部安全至关重要。在驾乘突发状况、人体受冲击时&#…...

Windows 安装 Xinference

Windows 安装 Xinference 0. 引言1. 创建虚拟环境2. 安装 pytorch3. 安装 llama_cpp_python4. 安装 chatglm-cpp5. 安装 Xinference6. 设置 model 路径7. 启动 Xinference8. 查看 Cluster Information 0. 引言 Xorbits Inference&#xff08;Xinference&#xff09;是一个性能…...

静态时序分析:SDC约束命令set_case_analysis详解

相关阅读 静态时序分析https://blog.csdn.net/weixin_45791458/category_12567571.html?spm1001.2014.3001.5482 目录 指定值 指定端口/引脚列表 简单使用 set_case_analysis命令用于对电路进行特定模式的设定&#xff0c;例如对于一个工作在正常模式下的芯片&#xff0c;…...

C++ · 代码笔记4 ·继承与派生

目录 前言010继承与派生简单例程020多级继承030使用using关键词更改访问权限040隐藏050派生类与基类成员函数同名时不构成重载060使用多级继承展示成员变量在内存中的分布情况071派生类在函数头调用基类构造函数072构造函数调用顺序080构造函数与析构函数的调用顺序091多重继承…...

解决uni-app中使用webview键盘弹起遮挡input输入框问题

这个平平无奇的回答&#xff0c;可能是全网最靠谱的解决方案。 这里我用的是vue3 setup .vue文件的方式 <view> <web-view :fullscreen"false" :webview-styles"{top: statusBarHeight40,height:height,progress: {color: green,height:1px } }"…...

Java注解介绍

Java注解 注解介绍元注解RetentionTargetDocumentedInherited接口类测试结果 注解介绍 Java注解&#xff08;Annotation&#xff09;是一种元数据&#xff08;Metadata&#xff09;的形式&#xff0c;它可以被添加到Java代码中的类、方法、变量、参数等元素上&#xff0c;以提…...

万字详解,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…...

挂耳式蓝牙耳机哪家的好用?购买耳机前必须了解的几大要点

随着健康意识的提升&#xff0c;越来越多的人开始热衷于运动。运动不仅能够增强体质&#xff0c;对于我们这些忙碌的上班族而言&#xff0c;它也是一种极佳的减压方式。经过一天的辛勤工作&#xff0c;能够在户外跑步&#xff0c;让汗水带走压力&#xff0c;实在是一种享受。在…...

CSS文本属性

CSS文本属性 1.文本颜色2.文本间距3. 文本修饰4 .文本缩进5.文本对齐_水平6.行高7. vertical-align 1.文本颜色 属性名&#xff1a;color作用&#xff1a;控制文字的颜色。可选值&#xff1a; 颜色名rgb或rgbaHEX或HEXA &#xff08;十六进制&#xff09;HSL或HSLA 开发中常用…...

MySQL篇—执行计划之覆盖索引Using index和条件过滤Using where介绍(第三篇,总共三篇)

☘️博主介绍☘️&#xff1a; ✨又是一天没白过&#xff0c;我是奈斯&#xff0c;DBA一名✨ ✌✌️擅长Oracle、MySQL、SQLserver、Linux&#xff0c;也在积极的扩展IT方向的其他知识面✌✌️ ❣️❣️❣️大佬们都喜欢静静的看文章&#xff0c;并且也会默默的点赞收藏加关注❣…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

ZYNQ学习记录FPGA(一)ZYNQ简介

一、知识准备 1.一些术语,缩写和概念&#xff1a; 1&#xff09;ZYNQ全称&#xff1a;ZYNQ7000 All Pgrammable SoC 2&#xff09;SoC:system on chips(片上系统)&#xff0c;对比集成电路的SoB&#xff08;system on board&#xff09; 3&#xff09;ARM&#xff1a;处理器…...

Linux安全加固:从攻防视角构建系统免疫

Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...