【动态规划】通配符匹配与正则表达式匹配

这篇具有很好参考价值的文章主要介绍了【动态规划】通配符匹配与正则表达式匹配。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、通配符匹配

题目描述:

给你一个输入字符串 (s) 和一个字符模式 § ,请你实现一个支持 ‘?’ 和 ‘*’ 匹配规则的通配符匹配:

  • ‘?’ 可以匹配任何单个字符。
  • ‘*’ 可以匹配任意字符序列(包括空字符序列)。
    判定匹配成功的充要条件是:字符模式必须能够 完全匹配 输入字符串(而不是部分匹配)。

示例 1:

输入:s = “aa”, p = “a”
输出:false
解释:“a” 无法匹配 “aa” 整个字符串。

示例 2:

输入:s = “aa”, p = ""
输出:true
解释:'
’ 可以匹配任意字符串。

示例 3:

输入:s = “cb”, p = “?a”
输出:false
解释:‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。

1.1 思路分析

我们可以分别以i和j表示s[0~i]p[0~j]是否能成功匹配。
【动态规划】通配符匹配与正则表达式匹配
那么这里就只用讨论ij的位置,有四种情况
1️⃣ 如果s[i] == p[j],那么我们就只用判断dp[i - 1][j - 1]是否能成功匹配,如果能成功匹配,那么说明加上ij的位置也能成功匹配。
状态转移方程:dp[i][j] = s[i] == p[j] && dp[i - 1][j - 1]
2️⃣ 如果p[j] == '?'那么说明此时s[i]不管是什么都可以,只需要判断dp[i - 1][j - 1]是否能成功匹配,就跟上面一样。
状态转移方程:dp[i][j] = p[j] == '?' && dp[i - 1][j - 1]
3️⃣ 如果p[j] == '*',这里的情况就比较多,因为它可以变成0个或多个字符:
【动态规划】通配符匹配与正则表达式匹配
这么多情况只要有一种情况满足条件即可。

状态转移方程:

for(int k = 0; k <= i; k++)
{
    if(dp[i - k][j - 1])
    {
        dp[i][j] = true;
        break;
    }
}

4️⃣ 如果p[j] != '?' && p[j] != '*' && p[j] != s[i],那么说明不能匹配。

1.2 初始化处理

我们看到状态转移方程会用到i-1j- 1,所以dp表可以多开一维,而为了不改变下标的映射关系,我们可以在s串和p串的开头各自添加一个字符。
接下来就是初始化,首先dp[0][0]就代表两个空串,一定能匹配。所以dp[0][0] = true;
其次还有*在p串开头的位置出现,因为*可以变成空串,所以只要是开头的*都可以跟s[0]匹配成功:dp[0][j] = true;

1.3 代码

class Solution {
public:
    bool isMatch(string s, string p) {
        s = " " + s;
        p = " " + p;
        int n = s.size(), m = p.size();
        vector<vector<bool>> dp(n, vector<bool>(m));
        dp[0][0] = true;
        for(int j = 1; j < m; j++)
        {
            if(p[j] == '*')
            {
                dp[0][j] = true;
            }
            else break;
        }
        for(int i = 1; i < n; i++)
        {
            for(int j = 1; j < m; j++)
            {
                if((p[j] == '?' && dp[i - 1][j - 1]))
                {
                    dp[i][j] = true;
                }
                else if(s[i] == p[j] && dp[i - 1][j - 1])
                {
                    dp[i][j] = true;
                }
                else if(p[j] == '*')
                {
                    for(int k = 0; k <= i; k++)
                    {
                        if(dp[i - k][j - 1])
                        {
                            dp[i][j] = true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[n - 1][m - 1];
    }
};

1.4 优化

p[j] == '*'这种情况其实可以写成:
【动态规划】通配符匹配与正则表达式匹配
而经过观察可以再写出一个式子:
【动态规划】通配符匹配与正则表达式匹配
经过观察可以发现蓝色框框圈起来的部分是相等的
【动态规划】通配符匹配与正则表达式匹配

所以可以写成:
【动态规划】通配符匹配与正则表达式匹配

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

二、正则表达式匹配

题目描述:

给你一个字符串 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
解释:".
” 表示可匹配零个或多个(‘*’)任意字符(‘.’)。

这里的.字符跟上面一道题的?作用是一样的。但是*字符又区别,它的作用是把*字符的前一个字符重复0次或者多次,比方说"a*"
它可以变成:"","a","aa","aaa"……

2.1 思路分析

这里的有些情况跟上面的重复:
dp[i - 1][j - 1] && (p[j] == '.' || s[i] == p[j])的时候,dp[i][j]=true
接下来只剩p[j] == '*' 的情况:
这里要分情况讨论j的前一个元素,如果前一个元素是.,那么也就是可以变成任意的多个字符,既然要匹配多个字符,那么又是跟上面一个题一样要讨论到底变成多长。因为上面讲过优化版,所以这里直接写:
【动态规划】通配符匹配与正则表达式匹配

接下来如果前面一个字符是普通字符:
【动态规划】通配符匹配与正则表达式匹配
这里解释以下:空自然不用说,当只变成长度为1的字符串时,首先要判断j的前一个字符是否等于s[i],如果不相等就不用考虑前面的了。

2.2 初始化设置

还是跟上面一样多加一维,然后让dp[0][0] = true,接下来就是看p的前面全部是x*x*……这种字符串的情况:文章来源地址https://www.toymoban.com/news/detail-470521.html

for(int j = 2; j < m; j += 2)
{
    if(p[j] == '*') dp[0][j] = true;
    else break;
}

2.3 代码

class Solution {
public:
    bool isMatch(string s, string p) {
        s = " " + s;
        p = " " + p;
        int n = s.size(), m = p.size();
        vector<vector<bool>> dp(n, vector<bool>(m + 1));
        dp[0][0] = true;
        for(int j = 2; j < m; j += 2)
        {
            if(p[j] == '*') dp[0][j] = true;
            else break;
        }
        for(int i = 1; i < n; i++)
        {
            for(int j = 1; j < m; j++)
            {
                if(p[j] == '*')
                {
                    if(p[j - 1] == '.')
                    {
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    }
                    else
                    {
                        dp[i][j] = dp[i][j - 2] || (s[i] == p[j - 1] && dp[i - 1][j]);
                    }
                }
                else 
                {
                    dp[i][j] = dp[i - 1][j - 1] && (p[j] == '.' || s[i] == p[j]);
                }
            }
        }
        return dp[n - 1][m - 1];
    }
};

到了这里,关于【动态规划】通配符匹配与正则表达式匹配的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Shell脚本攻略:通配符、正则表达式

    目录 一、理论 1.通配符 2.正则表达式 二、实验 1.通配符 2.正则表达式 (1)概念 通配符只用于匹配文件名、目录名等,不能用于匹配文件内容,而且是已存在的文件或者目录。 各个版本的shell都有通配符,这些通配符是一些特殊的字符, 用户可以在命令行的参数中使用这些

    2024年02月07日
    浏览(45)
  • python之[正则表达式]--通配符使用方法(最新可用)

    . 匹配任意字符,除了换行符 ^ 匹配字符串开始的位置 $ 匹配字符串结束的位置,当出现多组符合的匹配时,返回字符串最后的那组匹配 * 匹配 0,1,n 次 前面的原子【贪婪模式:尽可能多的匹配】 ? 匹配 0,1 次 前面的原子【懒惰模式:精确匹配】 + 匹配 1,n 次 前面的原子

    2024年02月07日
    浏览(56)
  • 【算法题】44. 通配符匹配

    给你一个输入字符串 (s) 和一个字符模式 (p) ,请你实现一个支持 \\\'?\\\' 和 \\\'*\\\' 匹配规则的通配符匹配: \\\'?\\\' 可以匹配任何单个字符。 \\\'*\\\' 可以匹配任意字符序列(包括空字符序列)。 判定匹配成功的充要条件是:字符模式必须能够 完全匹配 输入字符串(而不是部分匹配)。  

    2024年01月25日
    浏览(47)
  • LeetCode 44题:通配符匹配

    给你一个输入字符串 ( s ) 和一个字符模式 ( p ) ,请你实现一个支持  \\\'?\\\'  和  \\\'*\\\'  匹配规则的通配符匹配: \\\'?\\\'  可以匹配任何单个字符。 \\\'*\\\'  可以匹配任意字符序列(包括空字符序列)。 判定匹配成功的充要条件是:字符模式必须能够  完全匹配  输入字符串(而不是部

    2024年02月11日
    浏览(45)
  • 算法leetcode|44. 通配符匹配(rust重拳出击)

    给定一个字符串 ( s ) 和一个字符模式 ( p ) ,实现一个支持 \\\'?\\\' 和 \\\'*\\\' 的通配符匹配。 两个字符串 完全匹配 才算匹配成功。 说明: s 可能为空,且只包含从 a-z 的小写字母。 p 可能为空,且只包含从 a-z 的小写字母,以及字符 ? 和 * 。 面对这道算法题目,二当家的再次陷入了沉

    2023年04月09日
    浏览(39)
  • Spring Cloud Foundry上使用通配符模式匹配进行的安全绕过漏洞 CVE-2023-20873

    背景:公司项目扫描到 Spring Cloud Foundry上使用通配符模式匹配进行的安全绕过漏洞 CVE-2023-20873 CVE-2023-20873:在Cloud Foundry上使用通配符模式匹配进行的安全绕过 高风险 | 2023年5月18日 | CVE-2023-20873 在Spring Boot版本3.0.0 - 3.0.5, 2.7.0 - 2.7.10, 2.6.0 - 2.6.14, 2.5.0 - 2.5.14以及旧版支持的版本

    2024年02月09日
    浏览(67)
  • 动态规划学习——通符串匹配,正则表达式

    目录 ​编辑 一,通符串匹配 1.题目 2.题目接口 3,解题思路及其代码 二,正则表达  1.题目 2.题目接口 3.解题思路及其代码 三,交错字符串  1.题目 2,题目接口 3.解题思路及其代码 1.题目 给你一个输入字符串 ( s ) 和一个字符模式 ( p ) ,请你实现一个支持  \\\'?\\\'  和  \\\'*\\\'  匹

    2024年02月03日
    浏览(32)
  • 动态规划:LeetCode第10题 正则表达式匹配

    给你一个字符串  s  和一个字符规律  p ,请你来实现一个支持  \\\'.\\\'  和  \\\'*\\\'  的正则表达式匹配。 \\\'.\\\'  匹配任意单个字符 \\\'*\\\'  匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖  整个  字符串  s 的,而不是部分字符串。 1 = s.length = 20 1 = p.length = 20 s  只包含从 

    2024年04月11日
    浏览(28)
  • 【动态规划】【字符串】C++算法:正则表达式匹配

    视频算法专题 动态规划汇总 字符串 给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘ ’ 的正则表达式匹配。 ‘.’ 匹配任意单个字符 \\\' ’ 匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。 示例 1: 输入:

    2024年02月03日
    浏览(53)
  • 【面试算法——动态规划 21】正则表达式匹配(hard)&& 交错字符串

    链接: 10. 正则表达式匹配 给你一个字符串 s 和一个字符规律 p,请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。 ‘.’ 匹配任意单个字符 ‘*’ 匹配零个或多个前面的那一个元素 所谓匹配,是要涵盖 整个 字符串 s的,而不是部分字符串。 示例 1: 输入:s = “aa”

    2024年02月08日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包