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

代码随想录算法训练营Day 54 || 392.判断子序列、115.不同的子序列

392.判断子序列

力扣题目链接(opens new window)

给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。

示例 1:

  • 输入:s = "abc", t = "ahbgdc"
  • 输出:true

示例 2:

  • 输入:s = "axc", t = "ahbgdc"
  • 输出:false

提示:

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4

两个字符串都只由小写字符组成。


双指针法
  1. 初始化两个指针i 用于遍历字符串 sj 用于遍历字符串 t
  2. 遍历字符串 t:使用指针 j 遍历字符串 t,对于 t 中的每个字符,检查是否与 s 中的当前字符(由 i 指向)相匹配。
  3. 匹配字符:如果匹配(即 s[i] == t[j]),则将 ij 同时向前移动;如果不匹配,则只将 j 向前移动。
  4. 检查是否遍历完 s:如果 i 等于 s 的长度,说明 st 的子序列;如果 j 先达到 t 的末尾,则说明 s 不是 t 的子序列。
def isSubsequence(s: str, t: str) -> bool:i, j = 0, 0while i < len(s) and j < len(t):if s[i] == t[j]:i += 1j += 1return i == len(s)# 测试代码
s1, t1 = "abc", "ahbgdc"
s2, t2 = "axc", "ahbgdc"print(isSubsequence(s1, t1))  # 应该输出 True
print(isSubsequence(s2, t2))  # 应该输出 False

115.不同的子序列

力扣题目链接(opens new window)

给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,"ACE" 是 "ABCDE" 的一个子序列,而 "AEC" 不是)

题目数据保证答案符合 32 位带符号整数范围。

115.不同的子序列示例

提示:

  • 0 <= s.length, t.length <= 1000
  • s 和 t 由英文字母组成

动态规划思路解析

  1. 状态定义

    • dp[i][j] 表示考虑 s 的前 i 个字符和 t 的前 j 个字符时,t 作为 s 的子序列出现的次数。
  2. 状态初始化

    • dp[0][0] = 1:两个空字符串匹配的次数是1。
    • dp[i][0] = 1 对所有 i:如果 t 是空字符串,那么无论 s 是什么,都只有一种方式使 t 成为 s 的子序列(即全部删除 s)。
  3. 状态转移

    • 如果 s 的第 i 个字符与 t 的第 j 个字符相同(s[i - 1] == t[j - 1]),那么 t 的前 j 个字符可以在 s 的前 i - 1 个字符中找到对应的子序列,加上当前匹配的字符,形成新的子序列。同时,t 的前 j 个字符也可能在 s 的前 i - 1 个字符中出现多次,不包括 s[i]。因此,dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
    • 如果不同(s[i - 1] != t[j - 1]),则 s 的第 i 个字符不能用于匹配 t 的第 j 个字符。这时,dp[i][j] = dp[i - 1][j]
  4. 最终结果

    • dp[len(s)][len(t)] 是最终结果,表示 s 的前 len(s) 个字符中 t 的前 len(t) 个字符作为子序列出现的总次数。
def numDistinct(s: str, t: str) -> int:m, n = len(s), len(t)# 初始化一个 (m+1) x (n+1) 的 dp 矩阵dp = [[0] * (n + 1) for _ in range(m + 1)]# 当 t 为空字符串时,s 的子序列中总有一种方式使得 t 为其子序列for i in range(m + 1):dp[i][0] = 1# 填充 dp 矩阵for i in range(1, m + 1):for j in range(1, n + 1):if s[i - 1] == t[j - 1]:# 如果字符匹配,可以选择使用或不使用 s[i-1]dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]else:# 如果字符不匹配,只能选择不使用 s[i-1]dp[i][j] = dp[i - 1][j]return dp[m][n]# 测试代码
s = "babgbag"
t = "bag"
print(numDistinct(s, t))  # 应该输出 5

相关文章:

代码随想录算法训练营Day 54 || 392.判断子序列、115.不同的子序列

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

C 语言 gets()和puts()

C 语言 gets()和puts() gets()和puts()在头文件stdio.h中声明。这两个函数用于字符串的输入/输出操作。 C gets()函数 gets()函数使用户可以输入一些字符&#xff0c;然后按Enter键。 用户输入的所有字符都存储在字符数组中。 空字符将添加到数组以使其成为字符串。 gets()允…...

核—幂零分解

若向量空间 V \mathcal V V存在子空间 X \mathcal X X与 Y \mathcal Y Y&#xff0c;当 X Y V X ∩ Y 0 \mathcal {X\text{}Y\text{}V}\\ \mathcal {X}\cap \mathcal {Y}0 XYVX∩Y0 时称子空间 X \mathcal X X与 Y \mathcal Y Y是完备的&#xff0c;其中记为 X ⊕ Y V \ma…...

轻松掌控财务,分析账户花销,明细记录支出情况

随着科技的发展&#xff0c;我们的生活变得越来越智能化。然而&#xff0c;对于许多忙碌的现代人来说&#xff0c;管理财务可能是一件令人头疼的事情。复杂的账单、花销、收入&#xff0c;这些可能会让你感到无从下手。但现在&#xff0c;我们有一个全新的解决方案——一款全新…...

竞赛 题目:基于机器视觉opencv的手势检测 手势识别 算法 - 深度学习 卷积神经网络 opencv python

文章目录 1 简介2 传统机器视觉的手势检测2.1 轮廓检测法2.2 算法结果2.3 整体代码实现2.3.1 算法流程 3 深度学习方法做手势识别3.1 经典的卷积神经网络3.2 YOLO系列3.3 SSD3.4 实现步骤3.4.1 数据集3.4.2 图像预处理3.4.3 构建卷积神经网络结构3.4.4 实验训练过程及结果 3.5 …...

11. Spring源码篇之实例化前的后置处理器

简介 spring在创建Bean的过程中&#xff0c;提供了很多个生命周期&#xff0c;实例化前就是比较早的一个生命周期&#xff0c;顾名思义就是在Bean被实例化之前的处理&#xff0c;这个时候还没实例化&#xff0c;只能拿到该Bean的Class对象&#xff0c;如果在这个时候直接返回一…...

Python-Python高阶技巧:HTTP协议、静态Web服务器程序开发、循环接收客户端的连接请求

版本说明 当前版本号[20231114]。 版本修改说明20231114初版 目录 文章目录 版本说明目录HTTP协议1、网址1.1 网址的概念1.2 URL的组成1.3 知识要点 2、HTTP协议的介绍2.1 HTTP协议的概念及作用2.2 HTTP协议的概念及作用2.3 浏览器访问Web服务器的过程 3、HTTP请求报文3.1 H…...

P1304 哥德巴赫猜想

题目描述 输入一个偶数 N,验证 4∼N 所有偶数是否符合哥德巴赫猜想:任一大于 22 的偶数都可写成两个质数之和。如果一个数不止一种分法,则输出第一个加数相比其他分法最小的方案。例如 1010,10=3+7=5+510=3+7=5+5,则 10=5+510=5+5 是错误答案。 输入格式 第一行输入一个…...

CSDN每日一题学习训练——Python版(搜索插入位置、最大子序和)

版本说明 当前版本号[20231118]。 版本修改说明20231118初版 目录 文章目录 版本说明目录搜索插入位置题目解题思路代码思路参考代码 最大子序和题目解题思路代码思路参考代码 搜索插入位置 题目 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;…...

Java在物联网中的重要性

【点我-这里送书】 本人详解 作者:王文峰,参加过 CSDN 2020年度博客之星,《Java王大师王天师》 公众号:JAVA开发王大师,专注于天道酬勤的 Java 开发问题中国国学、传统文化和代码爱好者的程序人生,期待你的关注和支持!本人外号:神秘小峯 山峯 转载说明:务必注明来源(…...

动态规划解背包问题

题目 题解 def knapsac(W: int, N: int, wt: List[int], val: List[int]) -> int:# 定义状态动作价值函数: dp[i][j]&#xff0c;对于前i个物品&#xff0c;当前背包容量为j&#xff0c;最大的可装载价值dp [[0 for j in range(W1)] for i in range(N1)]# 状态动作转移for…...

PCL内置点云类型

PCL内置了许多点云类型供我们使用&#xff0c;下面先介绍PLC内置的点云数据类型 PCL中的点云类型为PointT&#xff1b;至于为什么是PointT类型需要追随到原来的ros开发中去&#xff0c;因为PCL库也是从原来的ROS中剥离出来的&#xff1b;大家都一致的认为点云结构是离散的N维信…...

clickhouse数据结构和常用数据操作

背景, 大数据中查询用mysql时间太长, 使用clickhouse 速度快, 数据写入mysql后同步到clickhouse中 测试1千万数据模糊搜索 mysql 需要30-40秒 clickhouse 约 100ms 一 数据结构和存储引擎 1 查看clickhouse所有数据类型 select * from system.data_type_families; 2 …...

upload-labs关卡9(基于win特性data流绕过)通关思路

文章目录 前言一、靶场需要了解的知识1::$data是什么 二、靶场第九关通关思路1、看源码2、bp抓包修改后缀名3、检查是否成功上传 总结 前言 此文章只用于学习和反思巩固文件上传漏洞知识&#xff0c;禁止用于做非法攻击。注意靶场是可以练习的平台&#xff0c;不能随意去尚未授…...

C++过河卒问题

#include <iostream> #include <cstring> using namespace std;int board[20][20]; // 棋盘 int dp[20][20][20][20]; // 动态规划数组int main() {int x0, y0, x1, y1;cin >> x0 >> y0 >> x1 >> y1; // 输入卒的起点和终点memset(board,…...

【机器学习12】集成学习

1 集成学习分类 1.1 Boosting 训练基分类器时采用串行的方式&#xff0c; 各个基分类器之间有依赖。每一层在训练的时候&#xff0c; 对前一层基分类器分错的样本&#xff0c; 给予更高的权重。 测试时&#xff0c; 根据各层分类器的结果的加权得到最终结果。 1.2 Bagging …...

nodeJs基础笔记

title: nodeJs基础笔记 date: 2023-11-18 22:33:54 tags: 1. Buffer 1. 概念 Buffer 是一个类似于数组的 对象 &#xff0c;用于表示固定长度的字节序列。 Buffer 本质是一段内存空间&#xff0c;专门用来处理 二进制数据 。 2. 特点 Buffer 大小固定且无法调整Buffer 性能…...

Skywalking流程分析_9(JDK类库中增强流程)

前言 之前的文章详细介绍了关于非JDK类库的静态方法、构造方法、实例方法的增强拦截流程&#xff0c;本文会详细分析JDK类库中的类是如何被增强拦截的 回到最开始的SkyWalkingAgent#premain try {/** 里面有个重点逻辑 把一些类注入到Boostrap类加载器中 为了解决Bootstrap类…...

矩阵的QR分解

矩阵的QR分解 GramSchmidt 设存在 B { x 1 , x 2 , … , x n } \mathcal{B}\left\{\mathbf{x}_{1},\mathbf{x}_{2},\ldots,\mathbf{x}_{n}\right\} B{x1​,x2​,…,xn​}在施密特正交化过程中 q 1 x 1 ∣ ∣ x 1 ∣ ∣ q_1\frac{x_1}{||x_1||} q1​∣∣x1​∣∣x1​​ q k …...

STL总结

STL vector 头文件<vector> 初始化,定义,定义长度&#xff0c;定义长度并且赋值&#xff0c;从数组中获取数据返回元素个数size()判断是否为空empty()返回第一个元素front()返回最后一个数back()删除最后一个数pop_back()插入push_back(x)清空clear()begin()end()使用s…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

HashMap中的put方法执行流程(流程图)

1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中&#xff0c;其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下&#xff1a; 初始判断与哈希计算&#xff1a; 首先&#xff0c;putVal 方法会检查当前的 table&#xff08;也就…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...

uniapp 实现腾讯云IM群文件上传下载功能

UniApp 集成腾讯云IM实现群文件上传下载功能全攻略 一、功能背景与技术选型 在团队协作场景中&#xff0c;群文件共享是核心需求之一。本文将介绍如何基于腾讯云IMCOS&#xff0c;在uniapp中实现&#xff1a; 群内文件上传/下载文件元数据管理下载进度追踪跨平台文件预览 二…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...