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

Java——不同的子序列

题目链接

leetcode在线oj题——不同的子序列

题目描述

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

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

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

题目示例

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

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

题目提示

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

解题思路

我们将问题分解为:s的前i个字符的子序列中 t的前j个字符 出现的个数
先创建一个二维数组,行代表t的每一个字符,列代表s的每一个元素
在这里插入图片描述
其中arr[i][j]就代表s的前i个字符的子序列中 t的前j个字符 出现的个数
例如arr[4][3]就是rabb的子序列中rab出现的次数

arr[3][0]代表rab的子序列中空字符串出现的次数,显然将所有的字符都删除后就是空字符串,因此是1

而arr[0][3]代表空字符串的子序列中rab出现的次数,显然是0

arr[0][0]代表空字符串的子序列中空字符串出现的次数,显然是1

那么起始状态如下:
在这里插入图片描述

那么,我们来考虑一下arr[i][j]等于多少

如果s中的第i个字符和t中的第j个字符不相等:

那么显然s需要删除最后一个字符才能够有可能和t相等,因此:
arr[i][j] = arr[i - 1][j]

例如s是racb,t是rac,必须要删除s的最后一个字符b,才有可能和t相等

如果s中的第i个字符和t中的第j个字符相等:

可以分为下面两种情况:

  • 不删除s中的第i个字符
  • 删除s中的第i个字符

如果不删除s中的第i个字符,我们就不用考虑t的最后一个字符了,只需要考虑s的前i - 1个字符的子序列中t的前j - 1个字符出现的次数
因此:
arr[i][j] = arr[i - 1][j - 1]
例如racb和rab,我们可以直接考虑rac的子序列中ra出现的次数

如果删除s中的第i个字符,那么就相当于s的前i - 1个字符的子序列中t的前j个字符出现的次数
arr[i][j] = arr[i - 1][j]

例如rabb和rab,当我们删除rabb的第二个b后,就相当于rab的子序列中rab出现的次数

因此,将这两种情况合并可以得到:
arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]
在这里插入图片描述

最后返回arr[row][col]即可

代码

class Solution {public int numDistinct(String s, String t) {int row = s.length();int col = t.length();int[][] arr = new int[row + 1][col + 1];arr[0][0] = 1;for (int i = 1; i <= row; i++) {arr[i][0] = 1;for (int j = 1; j <= col; j++) {if(s.charAt(i - 1) == t.charAt(j - 1)){arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];} else {arr[i][j] = arr[i - 1][j];}}}return arr[row][col];}
}

相关文章:

Java——不同的子序列

题目链接 leetcode在线oj题——不同的子序列 题目描述 给定一个字符串 s 和一个字符串 t &#xff0c;计算在 s 的子序列中 t 出现的个数。 字符串的一个 子序列 是指&#xff0c;通过删除一些&#xff08;也可以不删除&#xff09;字符且不干扰剩余字符相对位置所组成的新…...

Git 基本操作之Git GUI界面和git命令行如何选择

1. 为啥推荐使用git命令行 我发现公司有很多的同事都喜欢使用git的GUI界面工具&#xff0c;喜欢鼠标点点点就完成了代码的提交&#xff0c;这种方式的确是比较简单便捷&#xff0c;但是却存在风险。先上一个事故给大家醒醒脑。 VScode Git 界面操作引发的惨案 上面的惨案是VS…...

Python编程 动态爱心

作者简介&#xff1a;一名在校计算机学生、每天分享Python的学习经验、和学习笔记。 座右铭&#xff1a;低头赶路&#xff0c;敬事如仪 个人主页&#xff1a;网络豆的主页​​​​​​ 目录 前言 一.所用库 1.random简介 2.math 简介 3.tkinter库的简介 二.实际图 三.…...

JavaScript :基础语法

位置&#xff1a; HTML 中的 Javascript 脚本代码必须位于 <script> 与 </script> 标签之间。 JavaScript 输出方式 window.alert() 弹出警告框。document.write() 将内容写到 HTML 文档中。innerHTML 写入到 HTML 元素。console.log() 写入到浏览器的控制台。 …...

buu [AFCTF2018]Single 1

题目描述&#xff1a; Jmqrida rva Lfmz (JRL) eu m uqajemf seny xl enlxdomrexn uajiderc jxoqarerexnu. Rvada mda rvdaa jxooxn rcqau xl JRLu: Paxqmdyc, Mrrmjs-Yalanja mny oekay. Paxqmdyc-urcfa JRLu vmu m jxiqfa xl giaurexnu (rmusu) en dmnza xl jmrazxdeau. Lxd …...

Linux C++ 200行完成线程池类

文章目录1、atomic使用2、volatile关键字3、条件变量4、成员函数指针使用5、线程池6、主线程先退出对子线程影响7、return、exit、pthread_exit区别8、进程和线程的区别1、atomic使用 原子操作&#xff0c;不可分割的操作&#xff0c;要么完整&#xff0c;要么不完整。 #includ…...

C语言指针剖析(初阶) 最详细!

什么是指针&#xff1f;指针和指针类型野指针指针运算指针和数组二级指针指针数组什么是指针&#xff1f;指针是内存中一个最小单元的编号&#xff0c;也就是地址。1.把内存划分为一个个的内存单元&#xff0c;一个内存单元的大小是一个字节。2.每个字节都给定唯一的编号&#…...

AcWing语法基础课笔记 第三章 C++中的循环结构

第三章 C中的循环结构 学习编程语言语法是次要的&#xff0c;思维是主要的。如何把头脑中的想法变成简洁的代码&#xff0c;至关重要。 ——闫学灿 学习循环语句只需要抓住一点——代码执行顺序&#xff01; while循环 可以简单理解为循环版的if语句。If语句是判断一次&#xf…...

A simple freeD tracking protocol implementation written in golang

可以使用的go版本freed调试代码 可以通过udp发送和接收数据 What is freeD? freeD is a very simple protocol used to exchange camera tracking data. It was originally developed by Vinten and is now supported by a wide range of hard- and software including Unreal…...

简约精美电商小程序【源码好优多】

简介 一款开源的电商系统&#xff0c;包含微信小程序和H5端&#xff0c;为大中小企业提供移动电子商务优秀的解决方案。 后台采用Thinkphp5.1框架开发&#xff0c;执行效率、扩展性、稳定性值得信赖。并且Jshop小程序商城上手难度低&#xff0c;可大量节省定制化开发周期。 功…...

全网详解 .npmrc 配置文件:比如.npmrc的优先级、命令行,如何配置.npmrc以及npm常用命令等

文章目录1. 文章引言2. 简述.npmrc3. 配置.npmrc3.1 .npmrc配置文件的优先级3.2 .npmrc设置的命令行3.3 如何设置.npmrc4. 配置发布组件5. npm常用命令6. 重要备注6.1 yarn6.2 scope命名空间6.3 镜像出错1. 文章引言 今天在某低代码平台开发项目时&#xff0c;看到如下编译配置…...

从0开始学python -31

Python3 模块-1 在前面的几个章节中我们基本上是用 python 解释器来编程&#xff0c;如果你从 Python 解释器退出再进入&#xff0c;那么你定义的所有的方法和变量就都消失了。 为此 Python 提供了一个办法&#xff0c;把这些定义存放在文件中&#xff0c;为一些脚本或者交互…...

Jenkins的使用教程

介绍&#xff1a; Jenkins是一个开源软件项目&#xff0c;是基于Java开发的一种持续集成工具&#xff0c;用于监控持续重复的工作&#xff0c;旨在提供一个开放易用的软件平台&#xff0c;使软件的持续集成变成可能。 目的: 最重要目的就是把原来分散在各个机器上繁杂的工作全部…...

1.Maven的坐标和依赖

【maven坐标】1.groupId: 通常与域名反向一一对应2.artifactId: 通常使用实际项目名称3.version: 项目当前版本号4.packaging&#xff1a;maven项目的打包方式&#xff0c;默认是jar5.classifier: 定义构建输出的一些附属构件&#xff0c;例如&#xff1a;nexus-indexer-2.0.0.…...

Jenkins 笔记

Jenkins brew install jenkins-lts brew services restart jenkins-lts brew services stop jenkins-lts b999ff5683464346b6d083f894968121 l 软件构建自动化 &#xff1a;配置完成后&#xff0c;CI系统会依照预先制定的时间表&#xff0c;或者针对某一特定事件&#xff0c;…...

Python和Java语言,哪个更适合做自动化测试?

经常有测试新手问我&#xff1a;Python和Java语言&#xff0c;哪个更适合做自动化测试&#xff1f;本来想简单的回答一下的&#xff0c;但又觉得对不起大家对小编的信任。因此&#xff0c;小编今天专门写了一篇文章来回答这个问题。欢迎各位大佬补充~1、什么是自动化测试&#…...

互联网的路由选择协议

互联网的路由选择协议 文章目录互联网的路由选择协议路由选择协议的几个概念分层次路由选择协议内部网关协议RIP协议距离向量算法RIP协议的报文格式内部网关协议OSPFOSPF的报文格式✨OSPF的特点外部网关协议BGPBGP的报文格式参考本篇主要讨论的是路由表中的路由是如何得出来的。…...

接口幂等性处理

1.Token 机制&#xff1a; a首先客户端请求服务端&#xff0c;获取一个 token&#xff0c;每一次请求都获取到一个全新的 token&#xff08;当然这个 token 会有一个超时时间&#xff09;&#xff0c;将 token 存入 redis 中&#xff0c;然后将 token 返回给客户端。 b客户端…...

数字孪生智慧机场:透视数字化时代下的航空运营

在《智慧民航建设路线图》文件中&#xff0c;民航局明确指出&#xff0c;智慧机场是实现智慧民航的四个核心抓手之一。这一战略性举措旨在推进数字化技术与航空产业的深度融合&#xff0c;为旅客提供更加智能化、便捷化、安全化的出行服务&#xff0c;进一步提升我国民航发展的…...

SpringBoot 文件上传后查看404的问题和解决404后需要访问两次才能查看的问题

文件上传、图片上传的实现见这个&#xff1a; SpringBootVue 实现头像上传功能_Teln_小凯的博客-CSDN博客 在实现上面的功能后&#xff0c;发现查看图片的时候提示404&#xff0c;解决这个方法如下&#xff1a; 1、配置资源静态文件映射 第一个参数是页面请求的地址&#x…...

我的Taotoken账单分析如何帮助优化模型选型与token消耗

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 我的Taotoken账单分析如何帮助优化模型选型与token消耗 在集成多个大模型API到实际业务或开发流程中&#xff0c;一个常见的困惑是…...

从找石油到防灾害:地震勘探技术如何跨界守护城市安全?

地震勘探技术的跨界革命&#xff1a;从油气勘探到城市安全守护者 上世纪20年代&#xff0c;当第一批地球物理学家尝试用炸药激发地震波来寻找石油时&#xff0c;他们或许不会想到&#xff0c;这项技术会在百年后成为保护现代城市安全的"透视眼"。传统的地震勘探技术…...

网盘直链下载助手:解锁九大网盘下载速度的终极方案

网盘直链下载助手&#xff1a;解锁九大网盘下载速度的终极方案 【免费下载链接】Online-disk-direct-link-download-assistant 一个基于 JavaScript 的网盘文件下载地址获取工具。基于【网盘直链下载助手】修改 &#xff0c;支持 百度网盘 / 阿里云盘 / 中国移动云盘 / 天翼云盘…...

别再折腾源码编译了!Ubuntu 20.04下用apt-get一键安装Asterisk PBX(附SIP账号配置详解)

别再折腾源码编译了&#xff01;Ubuntu 20.04下用apt-get一键安装Asterisk PBX&#xff08;附SIP账号配置详解&#xff09; 如果你正在寻找一种快速搭建企业级电话系统的方法&#xff0c;那么Asterisk PBX绝对值得考虑。作为开源PBX领域的标杆&#xff0c;Asterisk提供了完整的…...

EDA验证与调试:从学术理论到工业落地的核心挑战与自动化未来

1. 从互联网先驱到EDA专家&#xff1a;Andreas Veneris的跨界之路在半导体设计这个高度专业化的领域&#xff0c;Andreas Veneris的经历显得格外独特。他既是多伦多大学电气与计算机工程及计算机科学系的教授&#xff0c;又是EDA&#xff08;电子设计自动化&#xff09;公司Ven…...

第七部分-容器安全与监控——33. 镜像安全

33. 镜像安全 1. 镜像安全概述 镜像是容器的基石&#xff0c;镜像安全问题直接影响容器运行时安全。镜像安全涵盖基础镜像选择、镜像构建过程、镜像存储和分发等环节。 ┌─────────────────────────────────────────────────…...

DS4Windows终极指南:让PS4/PS5手柄在Windows上完美工作的完整教程

DS4Windows终极指南&#xff1a;让PS4/PS5手柄在Windows上完美工作的完整教程 【免费下载链接】DS4Windows Like those other ds4tools, but sexier 项目地址: https://gitcode.com/gh_mirrors/ds/DS4Windows DS4Windows是一款功能强大的开源工具&#xff0c;专门解决Pl…...

【SITS 2026 K8s for ML合规框架】:通过CNCF AI WG审核的3层资源隔离模型(含YAML模板+准入控制器配置)

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;AI原生Kubernetes编排&#xff1a;SITS 2026 K8s for ML工作负载 SITS 2026 引入了专为机器学习工作负载深度优化的 AI-native Kubernetes 编排层&#xff0c;突破传统 K8s 在资源弹性、拓扑感知与训练…...

S7-1200 PLC 五大核心实验精讲:从振荡电路到浮点数运算的仿真实战

1. 从零开始搭建S7-1200仿真环境 第一次接触西门子S7-1200 PLC时&#xff0c;我被它强大的功能和复杂的软件界面吓到了。后来发现只要掌握几个关键步骤&#xff0c;仿真环境搭建其实比想象中简单得多。这里分享我的踩坑经验&#xff0c;帮你省去80%的摸索时间。 首先需要安装…...

易连EDI-EasyLink大文件传输测试报告

一、引言 在企业级数据交换场景中&#xff0c;大文件传输的稳定性和效率始终是核心关注点。随着供应链协同深化&#xff0c;企业之间在公网进行交换的数据早已超越传统订单、发票等结构化短报文&#xff0c;逐步扩展到&#xff1a;产品主数据&#xff08;含高清图片/3D模型&am…...