( 动态规划) 115. 不同的子序列 ——【Leetcode每日一题】

news/2024/4/15 6:48:21

❓115. 不同的子序列

难度:困难

给你两个字符串 st ,统计并返回在 s子序列t 出现的个数。

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

示例 1:

输入:s = “rabbbit”, t = “rabbit”
输出:3
解释:
如下所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
ra b bbit
rab b bit
rabb b it

示例 2:

输入:s = “babgbag”, t = “bag”
输出:5
解释:
如下所示, 有 5 种可以从 s 中得到 “bag” 的方案。
ba b g bag
ba bgba g
b abgb ag
ba b gb ag
babg bag

提示:

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

💡思路:动态规划

本题可以使用动态规划,可以将本题拆分,拆分成若干个子问题,只考虑其中一步;

如比较字符串 s 的第 i 个字符 和 字符串 t 的第 j 个字符

  • 如果 s[i] 等于 t[j]s 的第 i 个字符可取可不取,总个数为两者之和:
    1. 若取s的前i个字符串子序列t的前j个字符串出现的个数 等于 s的前i - 1个字符串子序列t的前j - 1个字符串出现的个数;
    2. 若不取s的前i个字符串子序列t的前j个字符串出现的个数 等于 s的前i - 1个字符串子序列t的前j个字符串出现的个数;
  • 如果 s[i] 不等于 t[j] ,则 s的前i个字符串子序列t的前j个字符串出现的个数 等于 s的前i - 1个字符串子序列t的前j个字符串出现的个数;

定义一个二维 dp 数组,dp[i][j] ,表示s的前i个字符串子序列t的前j个字符串出现的个数状态转移公式为:

  • s[i] == t[j],则:
    d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] + d p [ i − 1 ] [ j ] dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] dp[i][j]=dp[i1][j1]+dp[i1][j]
  • s[i] != t[j],则:
    d p [ i ] [ j ] = d p [ i − 1 ] [ j ] dp[i][j] = dp[i - 1][j] dp[i][j]=dp[i1][j]

示例2dp 数组如下:

在这里插入图片描述

⭐️ 空间优化

由上述状态转移公式可知,dp[i][j] 只与上一行有关,即只需要一维dp数组即可,但是要逆序遍历,此时的状态转移公式:

  • s[i] == t[j],则:
    d p [ j ] = d p [ j − 1 ] + d p [ j ] dp[j] = dp[j - 1] + dp[j] dp[j]=dp[j1]+dp[j]
  • s[i] != t[j],则:
    d p [ j ] = d p [ j ] dp[j] = dp[j] dp[j]=dp[j]

注意:若s 的长度小于t的长度,则一定不存在,返回 0 ;若长度相等,但字符串不等,则也是返回 0

🍁代码:(Java、C++)

Java

class Solution {public int numDistinct(String s, String t) {int m = s.length();int n = t.length();if(m < n || (m == n && !s.equals(t))) return 0;int[][] dp= new int[m + 1][n + 1];for(int i = 0; i <= m; i++) dp[i][0] = 1;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(s.charAt(i - 1) == t.charAt(j - 1)){dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];}else{dp[i][j] = dp[i - 1][j];}}}return dp[m][n];}
}

C++

class Solution {
public:int numDistinct(string s, string t) {int m = s.size();int n = t.size();if(m < n || (m == n && s != t)) return 0;vector<vector<unsigned int>> dp(m + 1, vector<unsigned int>(n + 1));for(int i = 0; i <= m; i++) dp[i][0] = 1;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){if(s[i - 1] == t[j - 1]){dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];}else{dp[i][j] = dp[i - 1][j];}}}return dp[m][n];}
};

⭐️ 空间优化
Java

class Solution {public int numDistinct(String s, String t) {int m = s.length();int n = t.length();if(m < n || (m == n && !s.equals(t))) return 0;int[] dp= new int[n + 1];dp[0] = 1;for(int i = 1; i <= m; i++){for(int j = n; j > 0; j--){if(s.charAt(i - 1) == t.charAt(j - 1)){dp[j] += dp[j - 1];}}}return dp[n];}
}

C++

class Solution {
public:int numDistinct(string s, string t) {int m = s.size();int n = t.size();if(m < n || (m == n && s != t)) return 0;vector<unsigned int> dp(n + 1);dp[0] = 1;for(int i = 1; i <= m; i++){for(int j = n; j > 0; j--){if(s[i - 1] == t[j - 1]){dp[j] += dp[j - 1];}}}return dp[n];}
};

🚀 运行结果:

在这里插入图片描述

🕔 复杂度分析:

  • 时间复杂度 O ( m ∗ n ) O(m*n) O(mn),其中 m 为数组s的长度,n 为数组t的长度。
  • 空间复杂度 O ( n ) O(n) O(n),空间优化只需 n+1的空间;优化前的空间复杂度为 O ( m ∗ n ) O(m*n) O(mn)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!

注: 如有不足,欢迎指正!


http://www.ppmy.cn/news/75077.html

相关文章

Linux---文件操作命令(touch、cat、more)

1. touch命令 可以通过touch命令创建文件 语法&#xff1a;touch [选项] Linux路径 touch命令&#xff0c;参数必填&#xff0c;表示要创建的文件路径&#xff0c;相对、绝对、特殊路径符均可以使用。 touch 命令不光可以用来创建文件&#xff08;当指定操作文件不存在时&a…

[比赛简介]Parkinson‘s Freezing of Gait Prediction

比赛链接&#xff1a;https://www.kaggle.com/competitions/tlvmc-parkinsons-freezing-gait-prediction 比赛简介 本次比赛的目标是检测步态冻结&#xff08;FOG&#xff09;&#xff0c;这是一种使人衰弱的症状&#xff0c;困扰着许多帕金森病患者。您将开发一个机器学习…

【内部类匿名内部类反射LambdaStream流的使用】

一、内部类和匿名内部类 匿名内内部类和lambda表达式主要的区别在于 1、匿名内部类他必须实现继承类的所有方法 2、匿名内部类在重写时有override标识&#xff0c;而lambda没有 3、lambda表达式继承的接口只能有一个抽象方法 在使用匿名内部类的过程中&#xff0c;我们需要注意…

2023年最新VMware 17+虚拟机详细配置安装【程序员使用指南】!!

文章目录 Vmware版本选择17Pro安装自定义安装填写对应的许可证正式安装虚拟机进行对应的配置配置镜像文件选择对应的语言&#xff1a;到这个界面&#xff0c;选择中文 安装结束连接对应的xshell Vmware版本选择17Pro安装 ● 最开始从这里出发 自定义安装 ● 记得自定义在自…

解决APP抓包问题「网络安全」

1.前言 在日常渗透过程中我们经常会遇到瓶颈无处下手&#xff0c;这个时候如果攻击者从APP进行突破&#xff0c;往往会有很多惊喜。但是目前市场上的APP都会为防止别人恶意盗取和恶意篡改进行一些保护措施&#xff0c;比如模拟器检测、root检测、APK加固、代码混淆、代码反调试…

使用JWT实现登录认证

一、介绍 1.1、Session、Cookie、Token区别 session&#xff1a;存储再服务端&#xff0c;无法引用与分布式场景&#xff0c;并且需要占用服务端的资源 cookie&#xff1a;存储再客户端&#xff0c;适用于分布式场景&#xff0c;但是存在安全问题&#xff0c;不支持垮域访问 t…

【多线程】什么是线程死锁?形成条件是什么?如何避免?

文章目录 一、什么是线程死锁二、线程死锁三、形成死锁的四个必要条件是什么四、如何避免线程死锁 一、什么是线程死锁 死锁是指两个或两个以上的进程&#xff08;线程&#xff09;在执行过程中&#xff0c;由于竞争资源或者由于彼此通信而造成的一种阻塞的现象&#xff0c;若…

STL --- 2、容器 set 和multiset

std::set 和 std::multiset 都是 STL 中的关联容器&#xff0c;用于存储一组有序的元素。 1、std::set 和 std::multiset 特点 &#xff08;1&#xff09;std::set 中每个元素的键值都唯一&#xff0c;而 std::multiset 中可以有多个相同的键值。 &#xff08;2&#xff09;s…

Linux搭建MQTT服务器(mosquitto)并使用

零、码仙励志 在路上&#xff0c;寻找一个继续的理由&#xff0c;寻找一个曾经的梦想。 一、Linux搭建MQTT服务器&#xff08;mosquitto&#xff09;并使用 1、安装依赖 yum install gcc-c cmake openssl-devel libuuid-devel c-ares-devel uuid-devel libwebsockets-devel…

HP打印機维护怎么找官方资料

关键词&#xff1a; “Removal and replacement” "part number" 范例 Removal and replacement A7W93 67033 Removal and replacement A7W93-67081 HP PageWide Enterprise, HP PageWide Managed - Removal and replacement: Service fluid container kit | H…

Linux之NetLink学习笔记

1.NetLink机制 NetLink是一种基于应用层跟内核态的通信机制&#xff0c;其特点是一种异步全双工的通信方式&#xff0c;支持内核态主动发起通信的机制。该机制提供了一组特殊的API接口,用户态则通过socket API调用。内核发送的数据再应用层接收后会保存在接收进程socket的缓存…

数据结构与算法之散列表详解

一、散列表概述 散列表&#xff08;Hash Table&#xff09;也叫哈希表&#xff0c;它是一种时间复杂度能够达到接近常数的数据结构&#xff0c;可以用来快速地存储和查找数据。散列表通过哈希函数来将键值对映射为一个索引值&#xff0c;然后通过这个索引值来在数组中访问对应…

【数据库】SQLServer报修表,维修表,反馈表三表连查

大家好&#xff0c;我是雷工&#xff01; 最近参与的一个SCADA项目&#xff0c;客户要求增加设备维保的功能&#xff0c;对设备的报修&#xff0c;维修&#xff0c;反馈过程进行记录查询&#xff0c;进一步提升企业的信息化能力。 该过程的实现是通过创建三个表分别记录报修-维…

【0196】共享内存管理结构(shmem)之创建共享内存分配机制(Shared Memory Allocation)(2)

文章目录 1. 共享内存段(Shared Memory Segment)1.1 设置指向共享内存的基本指针2. 创建共享内存分配机制相关文章: 【0195】共享内存管理结构(shmem)之概念篇(1) 【0

Linux下安装配置maven

1.安装以及配置maven 1.1.下载maven安装包 首先需要切换到自己需要安装的目录 把配置都放到了&#xff1a;/root路径下 1.2.解压下载好的maven包 tar -zxvf apache-maven-3.6.0-bin.tar.gzcp -r apache-maven-3.6.0 /usr/local/1.3.配置maven环境变量 1.3.1.在环境变量中…

maven安装与配置

这里写目录标题 一、maven的下载二、配置环境变量三、setting.xml文件配置四、idea集成maven 一、maven的下载 maven官网 我准备好的maven解压即用&#xff0c;提取码&#xff1a;0221 二、配置环境变量 (1) 我的电脑 -> 属性 -> 高级系统设置 -> 环境变量 -> …

Windows本地快速搭建SFTP服务共享文件【外网访问】

文章目录 1. 搭建SFTP服务器1.1 下载 freesshd服务器软件1.3 启动SFTP服务1.4 添加用户1.5 保存所有配置 2 安装SFTP客户端FileZilla测试2.1 配置一个本地SFTP站点2.2 内网连接测试成功 3 使用cpolar内网穿透3.1 创建SFTP隧道3.2 查看在线隧道列表 4. 使用SFTP客户端&#xff0…

算法Day09 | KMP,28. 实现 strStr() ,459.重复的子字符串

Day09 KMP28. 实现 strStr()459.重复的子字符串 KMP KMP是三个人人名缩写&#xff0c;用于在文本字符串text中搜索pattern字符串&#xff0c;返回在text中第一出现的位置。 算法做法就是在暴力匹配的基础上加速匹配。通过对pattern字符串求next数组(该数组也成为前缀表)&#…

gitlab建立新分支提交,cherry-pick部分更新

gitlab介绍 GitLab是一个基于Git的在线代码托管和协作平台&#xff0c;提供源代码管理、单元测试、CI/CD构建、代码审查等功能。它是一个开放源代码的Git仓库管理系统&#xff0c;使用 Ruby on Rails 构建GitLab 不仅具有自己的 Git 仓库管理系统&#xff0c;还具有很多其他的…

SpringSecurity权限管理基本概念和整体架构介绍

文章目录 一、权限管理1、认证2、授权3、对权限控制&#xff0c;现有的解决方案 二、SpringSecurity简介1、官方定义2、历史 三、整体架构1、认证AuthenticationManagerAuthenticationSecurityContextHolder 2、授权AccessDecisionManagerAccessDecisionVoterConfigAttribute 一…
最新文章