字符串正则匹配leetcode_正则在线检验

字符串正则匹配leetcode_正则在线检验原题链接给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。‘.’ 匹配任意单个字符‘*’ 匹配零个或多个前面的那一个元素所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。示例 1:输入:s = “aa” p = “a”输出:false解释:”a” 无法匹配 “aa” 整个字符串。示例 2:输入:s = “aa” p = “a*”输出:true解释:因为 ‘*’ 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题链接
给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。

示例 1:

输入:s = "aa" p = "a"
输出:false
解释:"a" 无法匹配 "aa" 整个字符串。
示例 2:

输入:s = "aa" p = "a*"
输出:true
解释:因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此,字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:

输入:s = "ab" p = ".*"
输出:true
解释:".*" 表示可匹配零个或多个('*')任意字符('.')。
示例 4:

输入:s = "aab" p = "c*a*b"
输出:true
解释:因为 '*' 表示零个或多个,这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:

输入:s = "mississippi" p = "mis*is*p*."
输出:false

提示:

0 <= s.length <= 20
0 <= p.length <= 30
s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。
保证每次出现字符 * 时,前面都匹配到有效的字符

题解

  1. 动态规划
    在这里插入图片描述
class Solution { 

static const int N = 1e3 + 10;
public:
bool isMatch(string s, string p) { 

int n = s.size(),m = p.size();
vector<vector<bool> >dp(n + 1,vector<bool> (m + 1));
dp[0][0] = true;
for(int i = 1;i <= m;i ++){ 

if(p[i - 1] == '*' && ((i - 1) & 1))
dp[0][i] = dp[0][i - 2];
}
for(int i = 1;i <= n;i ++){ 

for(int j = 1;j <= m;j ++){ 

if(p[j - 1] == '.' || p[j - 1] == s[i - 1])dp[i][j] = dp[i - 1][j - 1];
else if(p[j - 1] == '*'){ 

dp[i][j] = dp[i][j - 2];
if(s[i - 1] == p[j - 2] || p[j - 2] == '.')dp[i][j] = dp[i][j] | dp[i - 1][j];
}
}
}
return dp[n][m];
}
};
  1. dfs深搜
class Solution { 

public:
bool isMatch(string s, string p) { 

if(s.size() == 0 && p.size() == 0)return true;
else if(s.size() != 0 && p.size() == 0)return false;
else if(s.size() == 0 && p.size() != 0){ 

//s为空的时候 p有可能出现a*.*b* 等带有*号的情况
if(p.size() >= 2 && p[1] == '*' && isMatch(s,p.substr(2)))
return true;
}
else{ 

char a = s[0],b = p[0];
//当有*的时候可以选择匹配一个或者多个
if(p.size() >= 2 && p[1] == '*'){ 

if(a == b || b == '.')return isMatch(s.substr(1),p) || isMatch(s,p.substr(2));
else return isMatch(s,p.substr(2));
}
//但没*的时候只能一个一个匹配
else if(a == b || b == '.')return isMatch(s.substr(1),p.substr(1));
}
return false;
}
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168888.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 优先级队列的使用[通俗易懂]

    优先级队列的使用[通俗易懂]优先级队列(priorityqueue)中的元素可以按照任意的顺序插入,却总是按照排序的顺序进行检索。也就是说,无论何时调用remove方法,总会获得当前优先级队列中最小的元素.然后,优先级队列并没有对所有的元素进行排序。如果用迭代的方式处理这些元素,并不需要对它们进行排序。优先级队列使用了一个优雅且高效的数据结构,称为堆(heap)。堆事一个可以自我调整的二叉树,对树执行添加(add)和删除(

  • 免费php空间带域名,freehostia免费250MB无广告PHP空间可绑域名「建议收藏」

    免费php空间带域名,freehostia免费250MB无广告PHP空间可绑域名「建议收藏」freehostia是一个老牌的主机服务商,创建于2005年,不但提供收费主机及域名,也提供可无限续期的免费PHP空间。空间信息:空间大小:250M月流量:6G免费域名:无绑定域名:支持申请指南:1、进入freehostia空间官方网站:http://www.freehostia.com/。2、选择免费空间free套餐开始注册,如果你找不到,请直接打开此链接:http://www.freeho…

  • dex文件详解

    dex文件详解1、基本概念能被DVM虚拟机识别,加载并执行的文件格式2、生成dex文件1、通过IDE自动帮我们build生成2、手动通过dx命令去生成dex文件3、在手机上手动运行dex文件3、使用dx命令来生成dex文件首先得要先配置dx环境变量,这个环境变量怎么配呢?找到的sdk的安装目录,然后进入build-tools目录,这里是你电脑上的所有sdk的安装目录,随便选择一个进去,就可以知道dx.b

  • 女生学java软件开发怎么样?就业前景如何?

    女生学java软件开发怎么样?就业前景如何?学java目前现状是男生多于女生,从事java工作的也是男生多于女生,那么这种现状是说女生学java不好找工作吗?​  一、女生适合从事java吗?  在很多人的潜意识里,认为女生是不适合从事java工作的,因为他们觉得从事java工作的人逻辑性要相当的好,并且专业操作水平要高,而女生往往在这方面比较弱。其实这只是一种偏见,就像古代人觉得女子不该干涉朝政一样,女生也是适合从事java工作的,并且还能发挥自己的优势把java工作做得更好。  二、女生学java好找工作吗?  1.现在的女生

  • hadoop集群 secondary namenode 的作用,fsiamge和edit的关系「建议收藏」

    hadoop集群 secondary namenode 的作用,fsiamge和edit的关系「建议收藏」hadoop集群 secondary namenode 的作用,fsiamge和edit的关系

  • VCL组件之编辑控件「建议收藏」

    VCL组件之编辑控件「建议收藏」Note以后将用两种方式提及组件,以组件的名称或定义组件的VCL类的名称。可以说“Label组件用于……”或说“TLabel用于……”,这两种方式谈到的是同一组件。编辑控件(EditContro

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号