【动态规划篇】正则表达式与通配符：开启代码匹配的赛博奇幻之旅
本篇博主将给大家分享如何解答正则表达式与通配符匹配问题；干货满满，值得收藏呀；这两种匹配方式在 LeetCode 的题目中，可不会轻易让我们过关。题目往往会给出各种各样复杂的匹配规则和字符串场景，要求我们巧妙运用正则表达式或通配符的特性，编写出高效且正确的解决方案。
那么，下面我们就开启这场旅行吧！！！
欢迎拜访：羑悻的小杀马特.-ZEEKLOG博客
本篇主题：正则表达式与通配符匹配解答（绝对巧解）
制作日期：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(); vector<vector<int>> dp(m+1,vector<int>(n+1));+t1;+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(); vector<vector<bool>>dp(m+1,vector<bool>(n+1)); //初始化：+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(); vector<vector<bool>>dp(m+1,vector<bool>(n+1)); //初始化：+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]对应的*时候；如何更好的优化；以及怎么把写出来繁琐的状态方程图化成简短的代码（更要仔细慎重以免出错）。
总而言之；多画图多理解多分析多学习外加仔细仔细再仔细。
感谢大家关注本篇分享到此希望对大家有所帮助！！！
