leetcode 通配符匹配_匹配任意一个字符的通配符是

leetcode 通配符匹配_匹配任意一个字符的通配符是给定一个字符串 (s) 和一个字符模式 § ,实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。‘?’ 可以匹配任何单个字符。‘*’ 可以匹配任意字符串(包括空字符串)。两个字符串完全匹配才算匹配成功。说明:s 可能为空,且只包含从 a-z 的小写字母。p 可能为空,且只包含从 a-z 的小写字母,以及字符 ? 和 *。示例 1:输入:s = “aa”p = “a”输出: false解释: “a” 无法匹配 “aa” 整个字符串。示例 2:输入:s = “aa”p = “*

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

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

给定一个字符串 (s) 和一个字符模式 § ,实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。

‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任意字符串(包括空字符串)。
两个字符串完全匹配才算匹配成功。

说明:

s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 ? 和 *。

示例 1:

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

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。
示例 3:

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:

输入:
s = "acdcb"
p = "a*c?b"
输出: false

题解
f[i][j]代表s[1:i],p[1:j]是否匹配,如果p[j] == ‘?’或者p[j] == s[i]的话,那么p[j]一定要匹配字母,如果p[j] 是一个字母且p[j] != s[i]那么匹配失败,如果p[j] == ‘*’的话那么可以选择匹配一个字符或者不匹配。

class Solution { 
   
public:
    bool isMatch(string s, string p) { 
   
        int n = s.size(),m = p.size();
        vector<vector<int> >f(n + 1,vector<int>(m + 1));
        f[0][0] = true;
        for(int i = 1;i <= m;i ++){ 
   
            if(p[i - 1] == '*')f[0][i] = f[0][i - 1];
        }
        for(int i = 1;i <= n;i ++){ 
   
            for(int j = 1;j <= m;j ++){ 
   
                if(s[i - 1] == p[j - 1] || p[j - 1] == '?')f[i][j] = f[i - 1][j - 1];
                else if(p[j - 1] != '*')f[i][j] = false;
                else{ 
   
                    f[i][j] = f[i - 1][j] | f[i][j - 1];
                }
            }
        }

        return f[n][m];
    }
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

  • pytest报错_git代码提交流程

    pytest报错_git代码提交流程前言我们每天写完自动化用例后都会提交到git仓库,随着用例的增多,为了保证仓库代码的干净,当有用例新增的时候,我们希望只运行新增的未提交git仓库的用例。pytest-picked插件可以

  • 万能乘法速算法大全_小学数学加减乘除【速算法】都在这里! 寒假让孩子练一练…

    万能乘法速算法大全_小学数学加减乘除【速算法】都在这里! 寒假让孩子练一练…★需要电子版资料可直接拉至文末查看领取方式哈!小果老师说:很多小朋友的寒假生活已经开启啦!寒假的确可以好好玩一玩,但某种程度上该学习还是的学习一些的!因此,今天小果老师要给大家分享的内容是数学速算法,这些内容掌握以后就几乎不用担心那些简便运算没头绪啦!赶紧来看看然后为孩子收藏起来吧!01加法的神奇速算法一、加大减差法口诀前面加数加上后面加数的整数,减去后面加数与整数的差等于和。例题1376+98…

  • 三极管饱和的判断「建议收藏」

    三极管饱和的判断「建议收藏」三极管是电流放大器件,决定三极管是否饱和取决于Ib和Ic的相对大小,通常来讲Ic/Ib>hfe时,三极管饱和。因此导出以下结论:1.如何判断饱和?判断饱和时应该求出基级最大饱和电流IBS,然后再根据实际的电路求出当前的基级电流,如果当前的基级电流大于基级最大饱和电流,则可判断电路此时处于饱和状态。2.饱和的条件:1.集电极和

  • maven私库nexus2.14.1迁移到nexus3.1

    maven私库nexus2.14.1迁移到nexus3.1maven私库nexus2.14.1迁移到nexus3.1(含安装教程),亲测可用

  • 时序数据库Machbase「建议收藏」

    时序数据库Machbase「建议收藏」Background最近偶然接触到Machbase,发现相关信息很少,于是自己做了一些简单的了解,这里记录下,方便有兴趣的童靴参考哈。1、官方介绍Machbase是韩国的一家公司开发的一款类似InfluxDB、DolphinDB、TDengine等时序数据库产品,不开源,不过单机fog版可以免费试用,具体可以参考官方网站:https://www.machbase.com/product/edge;但是国外的网站访问不便,这里给个下载的链接,想试用的可以下载:下载链接:https://pan.

  • vb教程编程实例详解pdf_vb程序设计教程答案第四版实验

    vb教程编程实例详解pdf_vb程序设计教程答案第四版实验实验8-3VB程序题:设计一个如图2.8.4所示的应用程序,要求如下:(1.)单击“打开文件”按钮弹出一个通用对话框,选择文件后显示在文本框中(2).单击“保存文件”按钮后弹出通用对话框,确定文件名后保存。(3)单击“查找下一个”按钮后在文本文件中查找单词“VB”,找到后以高亮度显示。解题,画4个按钮,1个文本框控件,再加上一个通用对话框控件,代码如下:PrivateSub…

发表回复

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

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