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

力扣---通配符匹配

题目描述:

给你一个输入字符串 (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];}
}

提交结果:

相关文章:

力扣---通配符匹配

题目描述&#xff1a; 给你一个输入字符串 (s) 和一个字符模式 (p) &#xff0c;请你实现一个支持 ? 和 * 匹配规则的通配符匹配&#xff1a; ? 可以匹配任何单个字符。 * 可以匹配任意字符序列&#xff08;包括空字符序列&#xff09;。 判定匹配成功的充要条件是&#xff…...

Rust 原生类型

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、标量类型&#xff08;scalar type&#xff09;二、 复合类型&#xff08;compound type&#xff09;总结 前言 Rust 学习系列 &#xff0c;rust中的原生类…...

09、全文检索 -- Solr -- SpringBoot 整合 Spring Data Solr (生成DAO组件 和 实现自定义查询方法)

目录 SpringBoot 整合 Spring Data SolrSpring Data Solr的功能&#xff08;生成DAO组件&#xff09;&#xff1a;Spring Data Solr大致包括如下几方面功能&#xff1a;Query查询&#xff08;属于半自动&#xff09;代码演示&#xff1a;1、演示通过dao组件来保存文档1、实体类…...

C# CAD SelectionFilter下TypedValue数组

SelectionFilter是用于过滤AutoCAD实体的类&#xff0c;在AutoCAD中&#xff0c;可以使用它来选择具有特定属性的实体。构造SelectionFilter对象时&#xff0c;需要传入一个TypedValue数组&#xff0c;它用于定义选择规则。 在TypedValue数组中&#xff0c;每个元素表示一个选…...

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 &#xff0c;B 题&#xff0c;C 题没写出来&#xff0c;B 是一个排序去重&#xff0b;双指针&#xff0c;C题是要观察出一个数学结论&#xff08;因为数据范围太大&#xff0c;我暴力做直接超时了&#xff09; 排 6253 &#xff0c;表现分是 998 &…...

Redis面试题整理(持续更新)

1. 缓存穿透&#xff1f; 缓存穿透是指查询一个一定不存在的数据&#xff0c;如果从存储层查不到数据则不写入缓存&#xff0c;这将导致这个不存在的数据每次请求都要到 DB 去查询&#xff0c;可能导致DB挂掉&#xff0c;这种情况大概率是遭到了攻击。 解决方案&#xff1a; …...

一周学会Django5 Python Web开发-Django5 Hello World编写

锋哥原创的Python Web开发 Django5视频教程&#xff1a; 2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~共计14条视频&#xff0c;包括&#xff1a;2024版 Django5 Python we…...

讲解用Python处理Excel表格

我们今天来一起探索一下用Python怎么操作Excel文件。与word文件的操作库python-docx类似&#xff0c;Python也有专门的库为Excel文件的操作提供支持&#xff0c;这些库包括xlrd、xlwt、xlutils、openpyxl、xlsxwriter几种&#xff0c;其中我最喜欢用的是openpyxl&#xff0c;这…...

WEB APIs(1)

变量声明const&#xff08;修饰常量&#xff09; const优先&#xff0c;如react&#xff0c;基本const&#xff0c; 对于引用数据类型&#xff0c;可用const声明&#xff0c;因为储存的是地址 何为APIs 可以使用js操作HTML和浏览器 分类&#xff1a;DOM&#xff08;文档对象…...

C++重新入门-基本输入输出

C 的 I/O 发生在流中&#xff0c;流是字节序列。如果字节流是从设备&#xff08;如键盘、磁盘驱动器、网络连接等&#xff09;流向内存&#xff0c;这叫做输入操作。如果字节流是从内存流向设备&#xff08;如显示屏、打印机、磁盘驱动器、网络连接等&#xff09;&#xff0c;这…...

【C语言】解析刘谦春晚魔术《守岁共此时》

今年的春晚上刘谦表演了魔术《守岁共此时》&#xff0c;台上台下积极互动&#xff08;尤其是小尼&#xff09;&#xff0c;十分的有趣。刘谦老师的魔术不仅仅是他的高超手法&#xff0c;还有这背后的严谨逻辑&#xff0c;下面我们来用C语言来解析魔术吧。 源代码 #define _CRT…...

剑指offer——数值的整数次方

目录 1. 题目描述2. 一般思路2.1 有问题的思路2.2 全面但不高效的思路2.3 面试小提示 3. 全面又高效的思路 1. 题目描述 题目:实现函数 double Power(double base,int exponent)&#xff0c;求base 的exponent 次方。不得使用库函数&#xff0c;同时不需要考虑大数问题 2. 一般…...

Tied Block Convolution: 具有共享较薄滤波器的更简洁、更出色的CNN

摘要 https://arxiv.org/pdf/2009.12021.pdf 卷积是卷积神经网络&#xff08;CNN&#xff09;的主要构建块。我们观察到&#xff0c;随着通道数的增加&#xff0c;优化后的CNN通常具有高度相关的滤波器&#xff0c;这降低了特征表示的表达力。我们提出了Tied Block Convolutio…...

算法沉淀——BFS 解决 FloodFill 算法(leetcode真题剖析)

算法沉淀——BFS 解决 FloodFill 算法 01.图像渲染02.岛屿数量03.岛屿的最大面积04.被围绕的区域 BFS&#xff08;广度优先搜索&#xff09;解决 Flood Fill 算法的基本思想是通过从起始点开始&#xff0c;逐层向外扩展&#xff0c;访问所有与起始点相连且具有相同特性&#xf…...

wordpress外贸成品网站模板

首页大图slider轮播&#xff0c;橙色风格的wordpress外贸网站模板 https://www.zhanyes.com/waimao/6250.html 蓝色经典风格的wordpress外贸建站模板 https://www.zhanyes.com/waimao/6263.html...

如何使用六图一表七种武器

六图一表七种武器用于质量管理&#xff1a; 描述当遇到问题时应该用那张图来解决&#xff1a; 一、如果题目说出了质量问题需要找原因&#xff1f; 解&#xff1a;用因果图&#xff0c;因果图也称石川图或鱼骨图 二、如果要判断过程是否稳定受控&#xff1f; 解&#xff1a…...

阿里云游戏服务器租用费用价格组成,费用详单

阿里云游戏服务器租用价格表&#xff1a;4核16G服务器26元1个月、146元半年&#xff0c;游戏专业服务器8核32G配置90元一个月、271元3个月&#xff0c;阿里云服务器网aliyunfuwuqi.com分享阿里云游戏专用服务器详细配置和精准报价&#xff1a; 阿里云游戏服务器租用价格表 阿…...

【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篇】

&#x1f680; 作者 &#xff1a;“码上有前” &#x1f680; 文章简介 &#xff1a;前端高频面试题 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac; 前端高频面试题--git篇 往期精彩内容常用命令git add 和 git stage 有什么区别怎么使用git连接…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)

一、OpenBCI_GUI 项目概述 &#xff08;一&#xff09;项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台&#xff0c;其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言&#xff0c;首次接触 OpenBCI 设备时&#xff0c;往…...

xmind转换为markdown

文章目录 解锁思维导图新姿势&#xff1a;将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件&#xff08;ZIP处理&#xff09;2.解析JSON数据结构3&#xff1a;递归转换树形结构4&#xff1a;Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...