【动态规划篇】正则表达式与通配符：开启代码匹配的赛博奇幻之旅
【动态规划篇】正则表达式与通配符：开启代码匹配的赛博奇幻之旅
一·正则表达式与通配符匹配介绍：
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=" "+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();
vector<vector<bool>>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();
vector<vector<bool>>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]对应的*时候；如何更好的优化；以及怎么把写出来繁琐的状态方程图化成简短的代码（更要仔细慎重以免出错）。 总而言之；多画图多理解多分析多学习外加仔细仔细再仔细。
感谢大家关注本篇分享到此希望对大家有所帮助！！！
腾讯云开发者
