【面试算法——动态规划 21】不同的子序列（hard） 通配符匹配（hard）

115. 不同的子序列

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

链接：：https://leetcode.cn/problems/distinct-subsequences/

示例 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.状态表示*

dp[i][j] 表⽰：在字符串 s 的 [0, j] 区间内的所有⼦序列中，有多少个 t 字符串 [0,i] 区间内的⼦串.

2.状态转移方程
分析状态转移⽅程的经验就是根据「最后⼀个位置」的状况，分情况讨论。
对于 dp[i][j] ，我们可以根据 s1[i] 与 s2[j] 的字符分情况讨论：

  1. . 两个字符相同， s1[i] = s2[j] ：那么最⻓公共⼦序列就在 s1 的 [0, i - 1] 以 及 s2 的 [0, j - 1] 区间上找到⼀个最⻓的，然后再加上 s1[i] 即可。因此 dp[i][j] = dp[i - 1][j - 1] + 1 ；
  2. ii. 两个字符不相同， s1[i] != s2[j] ：那么最⻓公共⼦序列⼀定不会同时以 s1[i] 和 s2[j] 结尾。那么我们找最⻓公共⼦序列时，有下⾯三种策略：
    去 s1 的 [0, i - 1] 以及 s2 的 [0, j] 区间内找：此时最⼤⻓度为 dp[i - 1][j] ；
    去 s1 的 [0, i] 以及 s2 的 [0, j - 1] 区间内找：此时最⼤⻓度为 dp[i ] [j - 1] ；
    去s1 的 [0, i - 1] 以及 s2 的 [0, j - 1] 区间内找：此时最⼤⻓度为 dp[i - 1][j - 1]

我们要三者的最⼤值即可。但是我们细细观察会发现，第三种包含在第⼀种和第⼆种情况⾥⾯，但是我们求的是最⼤值，并不影响最终结果。因此只需求前两种情况下的最⼤值即可。
综上，状态转移⽅程为：

if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1 ;
if(s1[i] != s2[j]) dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

3. 初始化
a. 「空串」是有研究意义的，因此我们将原始 dp 表的规模多加上⼀⾏和⼀列，表⽰空串。
b. 引⼊空串后，⼤⼤的⽅便我们的初始化。
c. 但也要注意「下标的映射关系」，以及⾥⾯的值要「保证后续填表是正确的」。
当 s1 为空时，没有⻓度，同理 s2 也是。因此第⼀⾏和第⼀列⾥⾯的值初始化为 0 即可保证后续填表是正确的.

4. 填表顺序
根据「状态转移⽅程」得：从上往下填写每⼀⾏，每⼀⾏从左往右

5. 返回值
返回 dp[m][n]

代码：

  int numDistinct(string s, string t) {int m=t.size();int n=s.size();//dp[i][j]表示的是 以0~j范围内的所有s子序列中，有多少0~i的t字串vector<vector<double>> dp(m+1,vector<double>(n+1));for(int i=0;i<=n;i++) dp[0][i]=1; for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){dp[i][j]+=dp[i][j-1];if(t[i-1]==s[j-1]){dp[i][j]+=dp[i-1][j-1];}}}return dp[m][n];}

在这里插入图片描述

44. 通配符匹配

链接：https://leetcode.cn/problems/wildcard-matching/description/

给你一个输入字符串 (s) 和一个字符模式 § ，请你实现一个支持 ‘?’ 和 ‘’ 匹配规则的通配符匹配：
‘?’ 可以匹配任何单个字符。
'’ 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

示例 1：

输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。
示例 2：

输入：s = “aa”, p = ""
输出：true
解释：'’ 可以匹配任意字符串。
示例 3：

输入：s = “cb”, p = “?a”
输出：false
解释：‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。

1.状态表示*

dp[i][j] 表⽰： p 字符串 [0, j] 区间内的⼦串能否匹配字符串 s 的 [0, i] 区间内的⼦串

2.状态转移方程
⽼规矩，根据最后⼀个位置的元素，结合题⽬要求，分情况讨论：

  1. i. 当 s[i] == p[j] 或 p[j] == ‘?’ 的时候，此时两个字符串匹配上了当前的⼀个字符，只能从 dp[i -
    1][j - 1] 中看当前字符前⾯的两个⼦串是否匹配。只能继承上个状态中的匹配结果， dp[i][j] = dp[i][j - 1] ；
  2. ii. 当 p[j] == ‘*’ 的时候，此时匹配策略有两种选择：
    • ⼀种选择是： * 匹配空字符串，此时相当于它匹配了⼀个寂寞，直接继承状态 dp[i] [j - 1] ，此时 dp[i][j] = dp[i][j -1] ；
    • 另⼀种选择是： * 向前匹配 1 ~ n 个字符，直⾄匹配上整个 s1 串。此时相当于从 dp[k][j - 1] (0 <= k <= i) 中所有匹配情况中，选择性继承可以成功的情况。此时 dp[i][j] = dp[k][j - 1] (0 <= k <= i) ；
  3. iii. 当 p[j] 不是特殊字符，且不与 s[i] 相等时，⽆法匹配。 三种情况加起来，就是所有可能的匹配结果。

综上所述，状态转移⽅程为：

▪ 当 s[i] == p[j] 或 p[j] == ‘?’ 时： dp[i][j] = dp[i][j - 1] ；
▪ 当 p[j] == ‘*’ 时，有多种情况需要讨论： dp[i][j] = dp[k][j - 1] (0 <=k <= i) ；

重难点：
优化：当我们发现，计算⼀个状态的时候，需要⼀个循环才能搞定的时候，我们要想到去优化。优
化的⽅向就是⽤⼀个或者两个状态来表⽰这⼀堆的状态。通常就是把它写下来，然后⽤数学的⽅式
做⼀下等价替换：

当 p[j] == ‘*’ 时，状态转移⽅程为： dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 2][j - 1] …

我们发现 i 是有规律的减⼩的，因此我们去看看 dp[i - 1][j] ：
dp[i - 1][j] = dp[i - 1][j - 1] || dp[i - 2][j - 1] || dp[i - 3][j - 1] …
我们惊奇的发现， dp[i][j] 的状态转移⽅程⾥⾯除了第⼀项以外，其余的都可以⽤ dp[i -
1][j] 替代。因此，我们优化我们的状态转移⽅程为： dp[i][j] = dp[i - 1][j] ||dp[i][j - 1]

3. 初始化
由于 dp 数组的值设置为是否匹配，为了不与答案值混淆，我们需要将整个数组初始化为false 。
由于需要⽤到前⼀⾏和前⼀列的状态，我们初始化第⼀⾏、第⼀列即可。

◦ dp[0][0] 表⽰两个空串能否匹配，答案是显然的，初始化为 true 。

  • ◦ 第⼀⾏表⽰ s 是⼀个空串， p 串和空串只有⼀种匹配可能，即 p 串表⽰为 “**" ，此时
    也相当于空串匹配上空串。所以，我们可以遍历 p 串，把所有前导为 "    ” 的 p ⼦串和空串 的 dp 值设为 true 。
  • ◦ 第⼀列表⽰ p 是⼀个空串，不可能匹配上 s 串，跟随数组初始化即可。

4. 填表顺序
根据「状态转移⽅程」得：从上往下填写每⼀⾏，每⼀⾏从左往右

5. 返回值
返回 dp[m][n]

代码：

 bool isMatch(string s, string p) {int n=s.size();int m=p.size();vector<vector<bool>> dp(n+1,vector<bool>(m+1));//初始化dp[0][0]=1;for(int i=1;i<=m;i++){if(p[i-1]=='*') dp[0][i]=1;else break;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(p[j-1]=='?'||s[i-1]==p[j-1]){dp[i][j]=dp[i-1][j-1];}if(p[j-1]=='*'){// for(int z=0;z<=i;z++)// {//     if(dp[z][j-1])//     {//         dp[i][j]=dp[z][j-1];//         break;//     }// }//优化dp[i][j] = dp[i - 1][j] || dp[i][j - 1];}}}return dp[n][m];}

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【微服务】八. 统一网关gateway

【微服务】八. 统一网关gateway

8.1 网关作用介绍 网关功能&#xff1a; 身份认证和权限校验服务路由、负载均衡请求限流 网关的技术实现 在SpringCloud中网关的实现包括两种&#xff1a; gatewayzuul Zuul是基于Servlet的实现&#xff0c;属于阻塞式编程。而SpringCloudGateway则是基于Spring5中提供的Web…
阅读更多...
“元创新·智生成” 第15届企业数智化学习大会公布嘉宾阵容

“元创新·智生成” 第15届企业数智化学习大会公布嘉宾阵容

2023年是AIGC爆发年&#xff0c;与AI相关的创新应用迅速向各行各业渗透。 在企业培训领域&#xff0c;数字人、元宇宙等正逐渐成为企业在开展人才发展、业务培训等工作的工具&#xff0c;其高效、便捷、在线化、场景化等优势受到企业的热捧。在需求的推动下&#xff0c;企业培…
阅读更多...
springboot整合pi支付开发

springboot整合pi支付开发

pi支付流程图&#xff1a; 使用Pi SDK功能发起支付由 Pi SDK 自动调用的回调函数&#xff08;让您的应用服务器知道它需要发出批准 API 请求&#xff09;从您的应用程序服务器到 Pi 服务器的 API 请求以批准付款&#xff08;让 Pi 服务器知道您知道此付款&#xff09;Pi浏览器向…
阅读更多...
【Java 进阶篇】CSS语法格式详解

【Java 进阶篇】CSS语法格式详解

在前端开发中&#xff0c;CSS&#xff08;层叠样式表&#xff09;用于控制网页的样式和布局。了解CSS的语法格式是学习如何设计和美化网页的关键。本文将深入解释CSS的语法格式&#xff0c;包括选择器、属性和值等基本概念&#xff0c;同时提供示例代码以帮助初学者更好地理解。…
阅读更多...
微信小程序点单左右联动的效果实现

微信小程序点单左右联动的效果实现

微信小程序点单左右联动的效果实现 原理解析&#xff1a;   点击左边标签会跳到右边相应位置&#xff1a;点击改变rightCur值&#xff0c;转跳相应位置滑动右边&#xff0c;左边标签会跳到相应的位置&#xff1a;监听并且设置每个右边元素的top和bottom&#xff0c;再判断当…
阅读更多...
【Amazon】基于AWS云实例(CentOS 7.9系统)使用kubeadm方式搭建部署Kubernetes集群1.25.4版本

【Amazon】基于AWS云实例(CentOS 7.9系统)使用kubeadm方式搭建部署Kubernetes集群1.25.4版本

文章目录 前言实验架构介绍K8S集群部署方式说明使用CloudFormation部署EC2实例集群环境准备修改主机名并配置域名解析&#xff08;ALL节点&#xff09;禁用防火墙禁用SELinux加载br_netfilter模块安装ipvs安装 ipset 软件包同步服务器时间关闭swap分区安装Containerd 初始化集群…
阅读更多...
Linux: alsa-lib 插件简介

Linux: alsa-lib 插件简介

文章目录 1. 前言2. 分析背景3. Linux ALSA 框架4. alsa 声卡设备5. alsa-lib 简介5.1 alsa-lib 插件5.1.1 alsa-lib 插件概览5.1.2 alsa-lib 插件工作细节5.1.2.1 插件对象的创建和初始化5.1.2.2 插件对象处理数据的过程 5.1.3 alsa-lib 内置插件代码组织5.1.4 自定义 alsa-li…
阅读更多...
js中的原型链

js中的原型链

编写思路&#xff1a; 简单介绍构造函数介绍原型对象原型对象、实例的关系&#xff0c;从而引出原型链的基本概念 原型链基本思想是利用原型让一个引用类型继承另一个引用类型的属性和方法。 1. 什么是构造函数 构造函数本身跟普通函数一样&#xff0c;也不存在定义构造函数…
阅读更多...
图神经网络 GNN

图神经网络 GNN

之前经常看到图神经网络的内容&#xff0c;但是一直都觉得很难&#xff0c;就没有继续了解&#xff0c;现在抽空学习了一下&#xff0c;简单了解GNN是个什么东西&#xff0c;还没有进行代码实践&#xff0c;随着后续的学习&#xff0c;会继续更新代码的内容&#xff0c;这里先记…
阅读更多...
Linux动态链接库.so文件

Linux动态链接库.so文件

一、动态库和静态库的区别 库是一个二进制文件&#xff0c;包含的代码可以被程序调用&#xff0c;如标准库、线程库。Windows 和 Linux下的库文件格式不兼容。 Windows环境&#xff1a;静态库是 .lib 文件&#xff0c;共享库是 .dll 文件 Linux环境&#xff1a;静态库是 .a 文…
阅读更多...
数据结构与算法（八）：排序算法

数据结构与算法（八）：排序算法

参考引用 Hello 算法 Github&#xff1a;hello-algo 1. 选择排序 选择排序的工作原理非常直接&#xff1a;开启一个循环&#xff0c;每轮从未排序区间选择最小的元素&#xff0c;将其放到已排序区间的末尾&#xff0c;设数组的长度为 n 初始状态下&#xff0c;所有元素未排序&…
阅读更多...
HTTP协议的请求协议和响应协议的组成,HTTP常见的状态信息

HTTP协议的请求协议和响应协议的组成,HTTP常见的状态信息

HTTP协议 什么是协议 协议实际上是某些人或组织提前制定好的一套规范,大家只要都按照这个规范来就可以做到沟通无障碍 HTTP协议是W3C(万维网联盟组织)制定的一种超文本传输通信协议(发送消息的模板和数据的格式),除了传送字符串,还有声音、视频、图片等流媒体等超文本信息 …
阅读更多...
伦敦银最新走势不利怎么办

伦敦银最新走势不利怎么办

跟其他的投资品种一样&#xff0c;伦敦银的价格走势在不停的变化&#xff0c;而且由于本身产品具有较高的资金杠杆&#xff0c;所以万一行情走势变得不利&#xff0c;在很短的时间之内就会对投资者的账户造成严重损失&#xff0c;所以投资者应该对此作好充分的准备。 伦敦银的最…
阅读更多...
LabVIEW利用以太网开发智能液位检测仪

LabVIEW利用以太网开发智能液位检测仪

LabVIEW利用以太网开发智能液位检测仪 目前&#xff0c;工业以太网接口在国内外的发展已经达到了相当深入的程度&#xff0c;特别是在自动化控制和工业控制领域有着非常广泛的应用。在工业生产过程中&#xff0c;钢厂的连铸机是前后的连接环节&#xff0c;其中钢水从大钢包进入…
阅读更多...
Spring Boot如何配置CORS支持

Spring Boot如何配置CORS支持

Spring Boot如何配置CORS支持 CORS&#xff08;跨源资源共享&#xff09;是一种Web浏览器的安全性功能&#xff0c;用于控制网页上的脚本文件从不同的源加载其他网页资源。在开发现代Web应用程序时&#xff0c;通常需要跨域请求不同的资源&#xff0c;如API服务或其他Web应用程…
阅读更多...
一个tomcat下如何部署多个项目？

一个tomcat下如何部署多个项目？

1、不修改端口&#xff0c;部署多个项目 清楚tomcat目录结构的应该都知道&#xff0c;项目包是放在webapps目录下的&#xff0c;那能否在同一个tomcat的webapps目录下运行多个不同项目呢&#xff1f; 答案是可以的。 1、将多个项目包放入webapps文件夹下 2、修改conf下的serv…
阅读更多...
reactjs开发环境搭建

reactjs开发环境搭建

Reactjs是一个前端web页面应用开发框架工具集&#xff0c;其支持前端构建页面以及后端构建页面两种常用的开发场景&#xff0c;其中&#xff0c;支持reactjs的开发框架包括next.js、remix、gatsby以及其他&#xff0c;本文主要描述next.js开发环境的搭建&#xff0c;next.js是一…
阅读更多...
Verilog HDL阻塞赋值和非阻塞赋值笔记

Verilog HDL阻塞赋值和非阻塞赋值笔记

1. module test( input wire clk, input wire b, output reg a, output reg c ); always(posedge clk) begin ab; ca; end endmodule 上面的代码在vivado中综合后的电路为&#xff1a; 2. module test( input wire clk, input wire b, outp…
阅读更多...
springcloud之项目实战环境准备

springcloud之项目实战环境准备

写在前面 为了更好的学习springcloud&#xff0c;我们来一起开发一个实战项目&#xff0c;加深理解。 1&#xff1a;项目介绍 在开始项目实战之前先来做一个整体的项目介绍&#xff0c;从而能够让对项目的整体架构和模板有一个比较清晰的认知。 大家都知道双11&#xff0c;…
阅读更多...
JS进阶-原型

JS进阶-原型

原型 原型就是一个对象&#xff0c;也称为原型对象 构造函数通过原型分配的函数是所有对象所共享的 JavaScript规定&#xff0c;每一个构造函数都有一个prototype属性&#xff0c;指向另一个对象&#xff0c;所以我们也称为原型对象 这个对象可以挂载函数&#xff0c;对象实…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023