数学|【动态规划篇】正则表达式与通配符：开启代码匹配的赛博奇幻之旅

本篇博主将给大家分享如何解答正则表达式与通配符匹配问题；干货满满，值得收藏呀；这两种匹配方式在 LeetCode 的题目中，可不会轻易让我们过关。题目往往会给出各种各样复杂的匹配规则和字符串场景，要求我们巧妙运用正则表达式或通配符的特性，编写出高效且正确的解决方案。

那么，下面我们就开启这场旅行吧！！！

：羑悻的小杀马特.-CSDN博客羑悻的小杀马特.擅长C/C++题海汇总,AI学习,c++的不归之路,等方面的知识,羑悻的小杀马特.关注算法,c++,c语言,ubuntu,linux,数据结构领域.https://blog.csdn.net/2401_82648291?type=latelyhttps://blog.csdn.net/2401_82648291?type=latelyhttps://blog.csdn.net/2401_82648291?type=lately

欢迎拜访：羑悻的小杀马特.-CSDN博客

本篇主题：正则表达式与通配符匹配解答（绝对巧解）

制作日期：~~2025.02.03~~

隶属专栏：C/C++题海汇总

首先大家肯定有可能对正则表达式与通配符匹配有点陌生；那么下面我们通俗易懂介绍一下吧：

一·正则表达式与通配符匹配介绍：

1.1正则表达式匹配：

定义：用特定字符和规则组成模式，精准描述字符串特征，实现复杂字符串匹配、查找、替换等操作。
规则特点：规则丰富复杂，有元字符（如 . 匹配任意单个字符、* 匹配零个或多个前面元素等），可表达细致匹配要求。
应用场景：适用于对匹配精度要求高的场景，像数据验证（邮箱、手机号格式）、文本提取（从网页抓取特定信息）。

1.2 通配符匹配：

定义：使用简单符号代表任意字符或字符串来进行匹配。
规则特点：规则简单，常见通配符有 *（匹配任意数量任意字符）和 ?（匹配单个任意字符）。
应用场景：多用于文件搜索（如查找所有 .txt 文件）、简单文本筛选，对匹配精度要求相对低。

下面以两道经典匹配问题来带大家深入探究：

二.通配符匹配：

2.1题目简述：

测试用例：

示例 1：

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

示例 2：

输入：s = "aa", p = "*"
输出：true
解释：'*' 可以匹配任意字符串。

示例 3：

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

题目传送门： 44. 通配符匹配 - 力扣（LeetCode）

题意分析：

首先，我们先把题目的要求根据用例简述一下并呈现出来：

也就是拿p串去和s串进行匹配；其中s串只有小写字符；而p串多了?和*；即？随便匹配s的任意一个字符；而*可以匹配s中全部字符（包括空字符，空串）（是不是一开是大家就认为只要p有个*就可以完全匹配s了？？？然而如果p存在非* 的还要完成与s串中的字符进行匹配）

故这里空串的思想很重要；当然在匹配中也很重要（后面如果dp初始化也很重要）。

2.2解答思路：

这里我们做过一些动归的题目就很容易想到是字符串两个数组的dp问题了；如果没头绪可以做一做力扣的最长公共子序列问题（传送门：1143. 最长公共子序列 - 力扣（LeetCode））；就懂啦，这里就先不做解释了。

那就贴一下1143的解答代码：


class Solution {
public:
   //dp[i][j]表示t2的0-j及t1的0-i区间内最长公共子序列的长度
    int longestCommonSubsequence(string t1, string t2) {
         int m=t1.size();
         int n=t2.size();
         vectorint>> dp(m+1,vector<int>(n+1));
         t1=" "+t1;
         t2=" "+t2;
 //分情况：最后一个字符i j 对应值是否同：
 //同：dp[i-1][j-1]+1 不同：dp[i-1][j],dp[i][j-1]，dp[i-1][j-1]分别是只包含j 只包含i 两个都不包含；最后一个可优化
         for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
          //dp[i][j]=t1[i-1]==t2[j-1]?dp[i-1][j-1]+1:max(dp[i-1][j],dp[i][j-1]);
          dp[i][j]=t1[i]==t2[j]?dp[i-1][j-1]+1:max(dp[i-1][j],dp[i][j-1]);
 
            }
         }
         return dp[m][n];
    }
};

下面我们这个思路了；因此就走动态规划的那五步吧。

首先我们进行状态定义：

2.2.1状态定义：

dp[i][j]表示p串0-j区间能否匹配s串0-i区间的整个字符串

2.2.2状态方程书写：

先剧透一下，这里状态方程确实有点不好写；但是只要理解了就不算问题了；下面博主深入带大家分析分析一下：

根据我们老套路；从最后一个位置分情况向前推导：

我们p[j]位置的值要么是a-z 要么是？要么是*；因此我们可以从这三方面分析；下面画图来分析下：

下面就是优化方案：

因此我们的状态方程就得到了：

2.2.3 初始化：

这里我们采取引入空串的一一对应方式来；故在s p串前面都加上空格；这样dp与s p数组交错时候就不用错位了。

即当我们定义完dp的时候；加上这句代码：

s=' '+s,p=' '+p;

代码判断：


 dp[0][0]=1;
        for(int k=1;k<=n;k++)  {
            if(p[k]=='*') dp[0][k]=1;
            else break;
        }

2.2.4填表顺序：

这里里根据填表时用到的量可以发现是上下左右的顺序；即正常遍历即可。

2.2.5确定返回值：

即返回我们dp[m][n]即可。

2.3解答代码：


class Solution {
public:
 //思路：分 ？ a-z * 的三种情况 外加数学公式化简*的情况：
    bool isMatch(string s, string p) {
        int m=s.size();
        int n=p.size();
        vectorbool>>dp(m+1,vector<bool>(n+1));
        //初始化：
        s=' '+s,p=' '+p;
        //根据dp对应的定义分析填充第0行：
        dp[0][0]=1;
        for(int k=1;k<=n;k++)  {
            if(p[k]=='*') dp[0][k]=1;
            else break;
        }
            
        //填表：
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
               if(p[j]=='*') dp[i][j]=dp[i][j-1]||dp[i-1][j];
               else dp[i][j]=(s[i]==p[j]||p[j]=='?')&&dp[i-1][j-1];
            }
        }
       return dp[m][n];
    }
};

三·正则表达式匹配：

3.1题目简述：

测试用例：

示例 1：

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

示例 2:

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

示例 3：

输入：s = "ab", p = ".*"
输出：true
解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

注意事项：

也就是p的*前一定是a-z。

题目传送门： 10. 正则表达式匹配 - 力扣（LeetCode）

3.2解答思路：

和上面的通配符匹配相差不大；只不过是*前面必须要有.或者a-z；然后把？换成了.

因此我们就只详细分析一下*的情况就好。

下面我们就从不同于上面的地方即状态方程书写和初始化来分析：

状态方程表示：

初始化：

这里由于*的操作变了故只有当s串为空串的时候会发生变化；画图理解下：

代码判断：


dp[0][0]=1;
        for(int k=2;k<=n;k+=2) {
            if(p[k]=='*') dp[0][k]=1;
            else break;
        }

上下的都雷同通配符匹配问题啦；不做解释了。

3.3解答代码：


class Solution {
public:
    bool isMatch(string s, string p) {
        int m=s.size();
        int n=p.size();
        vectorbool>>dp(m+1,vector<bool>(n+1));
        //初始化：
        s=' '+s,p=' '+p;
        dp[0][0]=1;
        for(int k=2;k<=n;k+=2) {
            if(p[k]=='*') dp[0][k]=1;
            else break;
        }
        //填表：
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
               if(p[j]=='*') dp[i][j]=dp[i][j-2]||((s[i]==p[j-1]||p[j-1]=='.')&&dp[i-1][j]);
               else dp[i][j]=(s[i]==p[j]||p[j]=='.')&&dp[i-1][j-1];
            }
        }
  return dp[m][n];
    }
};

四·本篇小结：

博主通过对这两道题进行尝试解答以及分享题解的过程总结出：

对于题解我们更要侧重于怎么往这方面想也就是为什么这么做；而不是直接按照规则把代码套上去；侧重于多画图分析讨论如何能得出这样的做法；学习别人的优秀代码解法并引导自己如何往这方面想：比如当p[j]对应的*时候；如何更好的优化；以及怎么把写出来繁琐的状态方程图化成简短的代码（更要仔细慎重以免出错）。

总而言之；多画图多理解多分析多学习外加仔细仔细再仔细。

感谢大家关注本篇分享到此希望对大家有所帮助！！！

一·正则表达式与通配符匹配介绍：

1.1正则表达式匹配：

1.2 通配符匹配：

二.通配符匹配：

2.1题目简述：

2.2解答思路：

2.2.1状态定义：

2.2.2状态方程书写：

2.2.3 初始化：

2.2.4填表顺序：

2.2.5确定返回值：

2.3解答代码：

三·正则表达式匹配：

3.1题目简述：

3.2解答思路：

状态方程表示：

初始化：

3.3解答代码：

四·本篇小结：

评论记录：