力扣---通配符匹配
题目描述:
给你一个输入字符串 (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连接…...
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器的上位机配置操作说明
LBE-LEX系列工业语音播放器|预警播报器|喇叭蜂鸣器专为工业环境精心打造,完美适配AGV和无人叉车。同时,集成以太网与语音合成技术,为各类高级系统(如MES、调度系统、库位管理、立库等)提供高效便捷的语音交互体验。 L…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
