115.不同的子序列

给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数,结果需要对 109 + 7 取模。

示例 1:

输入:s = "rabbbit", t = "rabbit"
输出3
解释:
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案rabbbit
rabbbit
rabbbit

示例 2:

输入:s = "babgbag", t = "bag"
输出5
解释:
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案babgbag
babgbag
babgbag
babgbag
babgbag

提示:

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

思路:

dp[i][j]表示s的前s个字符中含有多少个t串的前j个字符,dp[0][0]表示两个空串匹配,所以赋值为1,同理,对于dp[[0~i][0]的数据全赋值为1。对于s[i]==t[j],分两种情况,要么使用s[i-1]这个字符进行匹配,要使用这个字符进行匹配的话,那么当且仅当t[j-1]也等于s[i-1]时才行,此时符合的情况等于dp[i-1][j-1],最后一个字符相同,比较前边的就是了。如果不使用s[i-1]时,那么就得从前边去找t[j-1]

,即dp[i-1][j]。如果s[i]!=t[j],dp[i][j]=dp[i-1][j];

代码:

class Solution {

  public int numDistinct(String s, String t) {

        int[][] dp = new int[s.length()+1][t.length()+1];

        int m = (int) Math.pow(10, 9) + 7;

        for (int i = 0; i <= s.length(); i++) {

            dp[i][0] = 1;

        }

        for (int i = 1; i <= s.length(); i++) {

            for (int j = 1; j <= t.length() && j <= i; 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[s.length()][t.length()];

    }

}

结果:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/523222.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Coding and Paper Letter(八十八)

系列重启之CPL。 1 Coding: 1.一个Python库用来分析城市路网的工具箱&#xff0c;城市形态分析工具。 Madina 2.SkyPilot&#xff1a;在任何云上运行 LLM、AI 和 Batch。 通过简单的界面即可实现最大程度的节省性能、最高的 GPU 可用性和托管执行。 skypilot 3.探索美国卫…

寻找排序数组中的最小值

题目描述 已知一个长度为 n 的数组&#xff0c;预先按照升序排列&#xff0c;经由 1 到 n 次 旋转 后&#xff0c;得到输入数组。例如&#xff0c;原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到&#xff1a; 若旋转 4 次&#xff0c;则可以得到 [4,5,6,7,0,1,2]若旋转 7 次…

企业信息化建设之MCS/WCS的知识点精讲

0、背景: 近日,再做售前方案的时候,碰到WMS和WCS的对接的场景,有同事质疑MCS和WMS不会对接,其实大家在日常工作中碰到的都是一套系统, MCS和WCS都是指仓储控制系统,不过它们的应用场景和功能有所不同。 在制造业中,MCS系统主要负责全厂物料的搬送路径指派和管理…

whatsapp 语音通话基本实现(二)

Whatsapp VoiceCall 客户端通过websocket连接到服务器&#xff0c;客户端发起语音通话请求&#xff0c;并且完成必要的协商之后&#xff0c;就可以直接将语音数据发送给服务器&#xff0c;服务器接收到对方的语音数据之后也会通过websocket将语音数据转发给客户端。 websocke…

RuoYi-Vue若依框架-在框架内用颜色选择器,页面显示色块

在用若依框架进行二次开发的时候写到自己的一个模块&#xff0c;其中涉及到颜色&#xff0c;我就想着是手动输入还是采用颜色选择器呢&#xff0c;考虑到后续涉及到另一个字段编码于时就采用了颜色选择器&#xff0c;选择完的颜色显示的是十六进制的颜色选择器&#xff0c;这时…

Transformers in Vision:A Survey 阅读笔记

ACM上的一篇综述&#xff0c;讨论Transformer在CV上的应用。 摘要&#xff1a; Among their salient benefits,Transformers enable modeling long dependencies between inputsequence elements and support parallel processing of sequence as compared to recurrent networ…

深度剖析:网络安全中的红蓝对抗策略

红蓝对抗 红蓝对抗服务方案 在蓝队服务中&#xff0c;作为攻击方将开展对目标资产的模拟入侵&#xff0c;寻找攻击路径&#xff0c;发现安全漏洞和隐患。除获取目标系统的关键信息&#xff08;包括但不限于资产信息、重要业务数据、代码或管理员账号等&#xff09;外&#x…

【移动安全】对webview漏洞的一些分析

这次分析的app如下&#xff1a; 打开发现该app发现需要登录界面&#xff1a; 拖进jadx看一下&#xff0c;先来看一下AndroidManifest.xml文件 发现有两个类是导出&#xff0c;再来分析这两个类 这个RegistrationWebView类利用webview.loadUrl进行加载网页 java public class…

Vue基础知识:声明式导航——跳转传参,声明式导航有哪几种路由传值方式,查询参数传参语法,动态路由传参语法,两者的区别

在跳转路由时&#xff0c;进行传值 1.查询参数传参 1.语法格式如下&#xff1a; to"/path?参数名值" 2.对应页面组件接收传递过来的值 $route.query.参数名 案例演示&#xff1a; 此时点击“跳转并携带参数”这个链接&#xff0c;就会跳转到search这个页面并携带参…

SpringCloud学习(10)-SpringCloudAlibaba-Nacos服务注册、配置中心

Spring Cloud Alibaba 参考文档 Spring Cloud Alibaba 参考文档 nacos下载Nacos 快速开始 直接进入bin包 运行cmd命令&#xff1a;startup.cmd -m standalone 运行成功后通过http://localhost:8848/nacos进入nacos可视化页面&#xff0c;账号密码默认都是nacos Nacos服务注…

断网了,还能 ping 通 127.0.0.1 吗?

什么是127.0.0.1 什么是 ping TCP发数据和ping的区别 为什么断网了还能 ping 通 127.0.0.1 ping回环地址和ping本机地址有什么区别 127.0.0.1 和 localhost 以及 0.0.0.0 有区别吗 总结 你女神爱不爱你 &#xff0c;你问她&#xff0c;她可能不会告诉你。 但网通不通 &#xf…

CLCD 流水线发布SpringBoot项目

目录 一、流水线 1.1 点击进入流水线 1.2 新建流水线 二、添加流水线 三、构建上传和构建镜像 ​编辑 四、Docker部署 一、流水线 1.1 点击进入流水线 1.2 新建流水线 二、添加流水线 三、构建上传和构建镜像 在构建上传里添加一个步骤&#xff1a;构建镜像&#xff0c;这…

房企如何驱动新“三驾马车”,穿越地产周期?

今年以来&#xff0c;房地产行业在不确定性的周期中&#xff0c;逐渐显露出部分确定性。 今年两会期间&#xff0c;住建部明确指出&#xff0c;构建发展新模式是破解房地产发展难题的治本之策&#xff0c;在新模式下今后拼的是高质量、新科技、好服务。可以说&#xff0c;国家…

Android与RN远程过程调用的原理

Android与RN远程过程调用的原理是通过通信协议进行远程过程调用。RPC(Remote Procedure Call)是分布式系统常见的一种通信方式&#xff0c;从跨进程到跨物理机已经有几十年历史。 在React Native中&#xff0c;通信机制是一个C实现的桥&#xff0c;打通了Java和JS,实现了两者的…

C++初阶---vector(STL)

1、vector的介绍和使用 1.1、vector的介绍 1. vector是表示可变大小数组的序列容器。 2. 就像数组一样&#xff0c;vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素 进行访问&#xff0c;和数组一样高效。但是又不像数组&#xff0c;它的大小是…

Spring——框架介绍

每一个Java技术中都会存在一个“核心对象”&#xff0c;这个核心对象来完成主要任务为了得到核心对象&#xff0c;需要创建若干个辅助对象&#xff0c;从而导致开发步骤增加JDBC中 JDBC 核心对象——PreparedStatement 通过DriverManager得到数据库厂商提供的Driver对象DriverM…

27.WEB渗透测试-数据传输与加解密(1)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;26.WEB渗透测试-BurpSuite&#xff08;五&#xff09; BP抓包网站网址&#xff1a;http:…

网络基础知识入门

目录 一、局域网与广域网 1、局域网 2、广域网 二、协议 1、概念 2、协议的理解 3、协议的分层 1、分层 2、OSI七层模型 三、网络传输基本流程 1、报头 2、局域网通信原理 3、跨网络传输流程 四、IP地址和MAC地址 1、IP地址 2、MAC地址 3、两者的区别 一、局域…

define的多种用法

一.宏的用法 当我们在计算一个数据的时候&#xff0c;这些数据里面有一些常量&#xff0c;比如说&#xff0c;圆周率&#xff0c;自然对出e&#xff0c;普朗克常量&#xff0c;光速这一类的。 例子: #include <stdio.h> #define PI 3.14 int main(){ double s,r2; pri…

虚拟机 ubuntu 20.04 git 设置代理的方法

前言 ubuntu 20.04 虚拟机中 Git 访问 github 或者其他的 git 仓库&#xff0c;大部分情况下速度很慢&#xff0c;并且容易掉线 如果 主机上使用了代理软件&#xff0c;但是虚拟机 ubuntu 中 Git 访问 git 仓库依旧是很慢 【问题】如何设置 虚拟机 ubuntu 的 Git 代理&#x…