力扣---通配符匹配
题目描述:
给你一个输入字符串 (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连接…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
人机融合智能 | “人智交互”跨学科新领域
本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...
Linux 下 DMA 内存映射浅析
序 系统 I/O 设备驱动程序通常调用其特定子系统的接口为 DMA 分配内存,但最终会调到 DMA 子系统的dma_alloc_coherent()/dma_alloc_attrs() 等接口。 关于 dma_alloc_coherent 接口详细的代码讲解、调用流程,可以参考这篇文章,我觉得写的非常…...
热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁
赛门铁克威胁猎手团队最新报告披露,数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据,严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能,但SEMR…...
WebRTC调研
WebRTC是什么,为什么,如何使用 WebRTC有什么优势 WebRTC Architecture Amazon KVS WebRTC 其它厂商WebRTC 海康门禁WebRTC 海康门禁其他界面整理 威视通WebRTC 局域网 Google浏览器 Microsoft Edge 公网 RTSP RTMP NVR ONVIF SIP SRT WebRTC协…...
高分辨率图像合成归一化流扩展
大家读完觉得有帮助记得关注和点赞!!! 1 摘要 我们提出了STARFlow,一种基于归一化流的可扩展生成模型,它在高分辨率图像合成方面取得了强大的性能。STARFlow的主要构建块是Transformer自回归流(TARFlow&am…...
