力扣---通配符匹配
题目描述:
给你一个输入字符串 (s) 和一个字符模式 (p) ,请你实现一个支持 '?' 和 '*' 匹配规则的通配符匹配:
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符序列(包括空字符序列)。
判定匹配成功的充要条件是:字符模式必须能够 完全匹配 输入字符串(而不是部分匹配)。
示例 1:
输入:s = "aa", p = "a"
输出:false
解释:"a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:s = "aa", p = "*"
输出:true
解释:'*' 可以匹配任意字符串。
示例 3:
输入:s = "cb", p = "?a"
输出:false
解释:'?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
提示:
0 <= s.length, p.length <= 2000
s 仅由小写英文字母组成
p 仅由小写英文字母、'?' 或 '*' 组成
思路描述:
对于大多数的字符串的题目,我们都可以使用动态规划来解决。同样,这个题目也可以使用动态规划。
因为存在两个字符串,因此,我们应该使用二维dp数组,dp[i][j]表示当s字符串的长度为i时,p字符串的长度为j时,此时是否能够匹配上,如果可以,就是true,否则就为false。
dp[i][j]的取值根据不同的情况,要考虑不同的策略求出,而其的取值必然与dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]的值有关(可以认为是动态规划的一种套路)。
当p字符串的第j号位置的字符为*时,第一、需要考虑前j-1个位置的子串是否与s的第i元素为结尾的子串是否匹配。第二、需要考虑前j个位置的子串是否与s的第i-1元素为结尾的子串是否匹配。取两者的“或”关系。
当p字符串的第j号位置的字符为?或者p字符串的第j号位置的字符和s字符串的第i号位置的字符相同时,直接就可以取dp[i-1][j-1]的值。
代码:
class Solution {public boolean isMatch(String s, String p) {int m = s.length();int n = p.length();boolean[][] dp = new boolean[m + 1][n + 1];dp[0][0] = true;for (int i = 1; i <= n; ++i) {if (p.charAt(i - 1) == '*') {dp[0][i] = true;} else {break;}}for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (p.charAt(j - 1) == '*') {dp[i][j] = dp[i][j - 1] || dp[i - 1][j];} else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];}}}return dp[m][n];}
}
提交结果:

相关文章:
力扣---通配符匹配
题目描述: 给你一个输入字符串 (s) 和一个字符模式 (p) ,请你实现一个支持 ? 和 * 匹配规则的通配符匹配: ? 可以匹配任何单个字符。 * 可以匹配任意字符序列(包括空字符序列)。 判定匹配成功的充要条件是ÿ…...
Rust 原生类型
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、标量类型(scalar type)二、 复合类型(compound type)总结 前言 Rust 学习系列 ,rust中的原生类…...
09、全文检索 -- Solr -- SpringBoot 整合 Spring Data Solr (生成DAO组件 和 实现自定义查询方法)
目录 SpringBoot 整合 Spring Data SolrSpring Data Solr的功能(生成DAO组件):Spring Data Solr大致包括如下几方面功能:Query查询(属于半自动)代码演示:1、演示通过dao组件来保存文档1、实体类…...
C# CAD SelectionFilter下TypedValue数组
SelectionFilter是用于过滤AutoCAD实体的类,在AutoCAD中,可以使用它来选择具有特定属性的实体。构造SelectionFilter对象时,需要传入一个TypedValue数组,它用于定义选择规则。 在TypedValue数组中,每个元素表示一个选…...
python 爬虫篇(3)---->Beautiful Soup 网页解析库的使用(包含实例代码)
Beautiful Soup 网页解析库的使用 文章目录 Beautiful Soup 网页解析库的使用前言一、安装Beautiful Soup 和 lxml二、Beautiful Soup基本使用方法标签选择器1 .string --获取文本内容2 .name --获取标签本身名称3 .attrs[] --通过属性拿属性的值标准选择器find_all( name , at…...
第十二周学习报告
比赛 参加了一场 div 2 ,B 题,C 题没写出来,B 是一个排序去重+双指针,C题是要观察出一个数学结论(因为数据范围太大,我暴力做直接超时了) 排 6253 ,表现分是 998 &…...
Redis面试题整理(持续更新)
1. 缓存穿透? 缓存穿透是指查询一个一定不存在的数据,如果从存储层查不到数据则不写入缓存,这将导致这个不存在的数据每次请求都要到 DB 去查询,可能导致DB挂掉,这种情况大概率是遭到了攻击。 解决方案: …...
一周学会Django5 Python Web开发-Django5 Hello World编写
锋哥原创的Python Web开发 Django5视频教程: 2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~共计14条视频,包括:2024版 Django5 Python we…...
讲解用Python处理Excel表格
我们今天来一起探索一下用Python怎么操作Excel文件。与word文件的操作库python-docx类似,Python也有专门的库为Excel文件的操作提供支持,这些库包括xlrd、xlwt、xlutils、openpyxl、xlsxwriter几种,其中我最喜欢用的是openpyxl,这…...
WEB APIs(1)
变量声明const(修饰常量) const优先,如react,基本const, 对于引用数据类型,可用const声明,因为储存的是地址 何为APIs 可以使用js操作HTML和浏览器 分类:DOM(文档对象…...
C++重新入门-基本输入输出
C 的 I/O 发生在流中,流是字节序列。如果字节流是从设备(如键盘、磁盘驱动器、网络连接等)流向内存,这叫做输入操作。如果字节流是从内存流向设备(如显示屏、打印机、磁盘驱动器、网络连接等),这…...
【C语言】解析刘谦春晚魔术《守岁共此时》
今年的春晚上刘谦表演了魔术《守岁共此时》,台上台下积极互动(尤其是小尼),十分的有趣。刘谦老师的魔术不仅仅是他的高超手法,还有这背后的严谨逻辑,下面我们来用C语言来解析魔术吧。 源代码 #define _CRT…...
剑指offer——数值的整数次方
目录 1. 题目描述2. 一般思路2.1 有问题的思路2.2 全面但不高效的思路2.3 面试小提示 3. 全面又高效的思路 1. 题目描述 题目:实现函数 double Power(double base,int exponent),求base 的exponent 次方。不得使用库函数,同时不需要考虑大数问题 2. 一般…...
Tied Block Convolution: 具有共享较薄滤波器的更简洁、更出色的CNN
摘要 https://arxiv.org/pdf/2009.12021.pdf 卷积是卷积神经网络(CNN)的主要构建块。我们观察到,随着通道数的增加,优化后的CNN通常具有高度相关的滤波器,这降低了特征表示的表达力。我们提出了Tied Block Convolutio…...
算法沉淀——BFS 解决 FloodFill 算法(leetcode真题剖析)
算法沉淀——BFS 解决 FloodFill 算法 01.图像渲染02.岛屿数量03.岛屿的最大面积04.被围绕的区域 BFS(广度优先搜索)解决 Flood Fill 算法的基本思想是通过从起始点开始,逐层向外扩展,访问所有与起始点相连且具有相同特性…...
wordpress外贸成品网站模板
首页大图slider轮播,橙色风格的wordpress外贸网站模板 https://www.zhanyes.com/waimao/6250.html 蓝色经典风格的wordpress外贸建站模板 https://www.zhanyes.com/waimao/6263.html...
如何使用六图一表七种武器
六图一表七种武器用于质量管理: 描述当遇到问题时应该用那张图来解决: 一、如果题目说出了质量问题需要找原因? 解:用因果图,因果图也称石川图或鱼骨图 二、如果要判断过程是否稳定受控? 解:…...
阿里云游戏服务器租用费用价格组成,费用详单
阿里云游戏服务器租用价格表:4核16G服务器26元1个月、146元半年,游戏专业服务器8核32G配置90元一个月、271元3个月,阿里云服务器网aliyunfuwuqi.com分享阿里云游戏专用服务器详细配置和精准报价: 阿里云游戏服务器租用价格表 阿…...
【C++】C++11上
C11上 1.C11简介2.统一的列表初始化2.1 {} 初始化2.2 initializer_list 3.变量类型推导3.1auto3.2decltype3.3nullptr 4.范围for循环5.final与override6.智能指针7. STL中一些变化8.右值引用和移动语义8.1左值引用和右值引用8.2左值引用与右值引用比较8.3右值引用使用场景和意义…...
【前端高频面试题--git篇】
🚀 作者 :“码上有前” 🚀 文章简介 :前端高频面试题 🚀 欢迎小伙伴们 点赞👍、收藏⭐、留言💬 前端高频面试题--git篇 往期精彩内容常用命令git add 和 git stage 有什么区别怎么使用git连接…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...
【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统
Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...
[拓扑优化] 1.概述
常见的拓扑优化方法有:均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有:有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...
起重机起升机构的安全装置有哪些?
起重机起升机构的安全装置是保障吊装作业安全的关键部件,主要用于防止超载、失控、断绳等危险情况。以下是常见的安全装置及其功能和原理: 一、超载保护装置(核心安全装置) 1. 起重量限制器 功能:实时监测起升载荷&a…...
