leetcode日记(34)通配符匹配

这道题做了很久很久……一开始我想用的方法是使用双指针,分别指向两数组,然后依次按照题目中的规则遍历,做了很久发现时间超限了!这是我最后超时的代码!

class Solution {
public:bool isMatch(string s, string p) {for(int i=0;i<s.size();i++){cout<<s<<" "<<p<<endl;if(s[i]!=p[i]&&p[i]!='?'&&p[i]!='*') return 0;if(s[i]==p[i]||(p[i]=='?'&&i<s.size())){bool g=isMatch(s.substr(i+1,s.size()),p.substr(i+1,p.size()));return g;}else if(p[i]=='*'){while(p[i+1]=='*'){p.erase(p.begin()+i+1);}for(int j=0;j<=s.size()-i;j++){if(isMatch(s.substr(i+j,s.size()),p.substr(i+1,p.size()))==1) return 1;}}else return 0;}if(s==""&&p!=""){while(p[0]=='*') p.erase(p.begin());if(p=="") return 1;}if(s!=""&&p=="") return 0;if(s==""&&p=="") return 1;return 0;}
};

然后看了一眼解析…发现了很新奇很简单的思路!就是用bool数组记录前n个字符串是否匹配,然后使用动态规划依次填写bool数组。

期间遇到了一个小困难,就是*符号可以对应0个字母,可以每次判断正确都查看后一个字母是否为*,如果是则下一个也为正确

代码如下:

class Solution {
public:bool isMatch(string s, string p){int x=s.size(),y=p.size();bool b[x+1][y+1];for(int i=0;i<=x;i++)for(int j=0;j<=y;j++) b[i][j]=0;b[0][0]=1;int g=1;while(p[g-1]=='*'&&g<=y){b[0][g]=1;cout<<0<<" "<<g<<endl;g++;}for(int j=1;j<=y;j++){for(int i=1;i<=x;i++){if(b[i-1][j-1]!=0){if(s[i-1]==p[j-1]||p[j-1]=='?'){b[i][j]=1;int u=j+1;while(p[u-1]=='*'&&u<=y){b[i][u]=1;u++;}}else if(p[j-1]=='*'){for(int o=i;o<=x;o++){b[o][j]=1;int u=j+1;while(p[u-1]=='*'&&u<=y){b[i][u]=1;u++;}}}}}}cout<<x<<" "<<y;return b[x][y];}
};

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

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

相关文章

【C语言】指针详细解读1

1. 内存和地址 1.1 内存 在讲述内存之前&#xff0c;我们先拿生活中的例子类比一下&#xff1a; 假如我们要寻找酒店的一位朋友&#xff0c;首先我得知道以下一些信息&#xff1a;知道他是人&#xff0c;知道酒店名&#xff0c;知道酒店房间号。人就表示我们不能去找其他的…

鸿蒙Harmony应用开发—ArkTS声明式开发(通用属性:Flex布局)

说明&#xff1a; 从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 仅当父组件是 Flex、Column、Row 、GridRow时生效。 flexBasis flexBasis(value: number | string) 设置组件的基准尺寸。 卡片能力&#xff1a; 从A…

【MySQL】学习多表查询和笛卡尔积 - 副本

](https://img-blog.csdnimg.cn/21dd41dce63a4f2da07b9d879ad0120b.png#pic_center) ??个人主页: ??热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 ??个人格言:“没有罗马,那就自己创造罗马~” #mermaid-svg-N8PeTKG6uLu4bJuM {font-family:“trebuchet ms”,…

手写数字识别(慕课MOOC人工智能之模式识别)

问题&#xff1a;手写数字识别 数据集 数据集链接请点击我 代码 %mat2vector.m function [data_] mat2vector(data,num)[row,col,~] size(data);data_zeros(num,row*col);for page 1:numfor rows 1:rowfor cols1:coldata_(page,((rows-1)*colcols)) im2double(data(rows,cols…

移动互联网时代的APP上架流程和要点

摘要 本文将介绍移动应用程序上架的基本流程和要点&#xff0c;包括应用商店注册、APP材料准备、打包上传App、APP审核以及发布APP的详细步骤。此外&#xff0c;还会提到利用appuploder工具简化iOS应用上架步骤的方法&#xff0c; 引言 在移动互联网时代&#xff0c;开发一…

【JavaEE】_HttpServletResponse类

目录 1. 核心方法 2. 关于setStatus(400)与sendError 2.1 setStatus(400) 2.2 sendError 3. setHeader方法 4. 构造重定向响应 4.1 使用setHeader和setStatus实现重定向 4.2 使用sendRedirect实现重定向 本专栏已有文章介绍HttpServlet和HttpServletRequest类&#…

加密与安全_探索对称加密算法

文章目录 概述常用的对称加密算法AESECB模式CBC模式 (推荐)ECB VS CBC 附&#xff1a;AES工具类总结 概述 对称加密算法是一种加密技术&#xff0c;使用相同的密钥来进行加密和解密数据。在这种算法中&#xff0c;发送方使用密钥将明文&#xff08;未加密的数据&#xff09;转…

【HDFS】Decommision(退役) EC数据节点剩最后几个块卡住的问题

一、背景 近期操作退役EC集群的节点。在退役的过程中,遇到了一些问题。特此总结一下。 本文描述的问题现象是: 每一批次退役10个节点,完全退役成功后开始操作下一批。 但是,中间有一批次有2台节点的Under Replicated Blocks一直是1,不往下降。 处于Decommissioning状态卡…

使用docker方式测试部署django项目(客户催)

需求 1&#xff1a;已有django项目–weidanyewu 2&#xff1a;希望在服务器上测试部署–客户催 3&#xff1a;没完善django的启动 4&#xff1a;使用临时数据库进行演示 5&#xff1a;使用python3.10版本镜像 6&#xff1a;展示端口80 7&#xff1a;后台执行django程序 8&#…

MATLAB练习题:排队论问题的模拟

​讲解视频&#xff1a;可以在bilibili搜索《MATLAB教程新手入门篇——数学建模清风主讲》。​ MATLAB教程新手入门篇&#xff08;数学建模清风主讲&#xff0c;适合零基础同学观看&#xff09;_哔哩哔哩_bilibili 下面我们来看一道排队论的题目。假设某银行工作时间内只有一个…

【前端素材】推荐优质后台管理系统网页Highdmin平台模板(附源码)

一、需求分析 1、系统定义 后台管理系统是一种用于管理和控制网站、应用程序或系统的管理界面。它通常被设计用来让网站或应用程序的管理员或运营人员管理内容、用户、数据以及其他相关功能。后台管理系统是一种用于管理网站、应用程序或系统的工具&#xff0c;通常由管理员使…

如何搭建自己的图床

前言 简单来说&#xff0c;图床是一种在线服务&#xff0c;允许用户上传、存储和分享图片。当把图片上传到该服务器上后&#xff0c;便能在互联网上通过链接来使用该图片&#xff0c;尤其是在不允许直接上传图片文件的平台上&#xff0c;也有些平台不允许上传其他平台的图片文…

【Web】青少年CTF擂台挑战赛 2024 #Round 1 wp

好家伙&#xff0c;比赛结束了还有一道0解web题是吧( 随缘写点wp(简单过头&#xff0c;看个乐就好) 目录 EasyMD5 PHP的后门 PHP的XXE Easy_SQLi 雏形系统 EasyMD5 进来是个文件上传界面 说是只能上传pdf&#xff0c;那就改Content-Type为application/pdf&#xff0c;改…

【Django】执行查询—跨关系查询中的跨多值关联问题

跨多值查询 跨越 ManyToManyField 或反查 ForeignKey &#xff08;例如从 Blog 到 Entry &#xff09;时&#xff0c;对多个属性进行过滤会产生这样的问题&#xff1a;是否要求每个属性都在同一个相关对象中重合。 filter() 先看filter()&#xff0c;通过一个例子看&#xf…

Java 学习和实践笔记(26):组合(component)的含义以及与继承(extends)的关系

组合的两个作用&#xff1a; 1&#xff09;通过将父类对象作为子类的属性 2&#xff09;通过第1点的作用&#xff0c;实现了代码复用。 示例代码&#xff1a; public class TestComponent {public static void main(String[] args) {Student2 s1 new Student2("jason&…

MySQL 存储过程批量插入总结

功能需求背景&#xff1a;今天接到产品经理核心业务表的数据压测功能&#xff0c;让我向核心业务表插入百万级的业务量数据&#xff0c;我首先想到的办法就是存储过程实现数据的批量 。 由于无法提供核心业务表&#xff0c;本文仅仅提供我刚刚自己创建的表bds_base_user 表做相…

缓存穿透解决方案之布隆过滤器

布隆过滤器可以快速判断数据是否存在&#xff0c;避免从数据库中查询数据是否存在&#xff0c;减轻数据库的压力 布隆过滤器是由一个初值为0的bit数组和N个哈希函数&#xff0c;可以用来快速的判断某个数据是否存在 当我们想要标记某个数据是否存在时&#xff0c;布隆过滤器会…

FPGA之带有进位逻辑的加法运算

module ADDER&#xff08; input [5&#xff1a;0]A&#xff0c; input [5&#xff1a;0]B&#xff0c;output[6&#xff1a;0]Q &#xff09;&#xff1b; assign Q AB&#xff1b; endmodule 综合结果如下图所示&#xff1a; 使用了6个Lut&#xff0c;&#xff0c;6个LUT分布…

2023年全国职业院校技能大赛中职组大数据应用与服务赛项题库参考答案陆续更新中,敬请期待…

2023年全国职业院校技能大赛中职组大数据应用与服务赛项题库参考答案陆续更新中&#xff0c;敬请期待… 武汉唯众智创科技有限公司 2024 年 2 月 联系人&#xff1a;辜渝傧13037102709 题号&#xff1a;试题01 模块三&#xff1a;业务分析与可视化 &#xff08;一&#xff0…

ONLYOFFICE 桌面编辑器 v8.0 更新内容详细攻略

文章目录 引言PDF 表单RTL 支持电子表格中的新增功能Moodle 集成用密码保护 PDF 文件从“开始”菜单快速创建文档本地界面主题下载安装桌面编辑工具总结 引言 官网链接&#xff1a; ONLYOFFICE 官方网址 ONLYOFFICE 桌面编辑器是一款免费的文档处理软件&#xff0c;适用于 Li…