1.题目基本信息
1.1.题目描述
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。
- ‘.’ 匹配任意单个字符
- ‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s 的，而不是部分字符串。
1.2.题目地址
https://leetcode.cn/problems/regular-expression-matching/description/
2.解题方法
2.1.解题思路
动态规划
2.2.解题步骤
第一步，状态定义；dp[i][j]为s的前i个字符串和p的前j个字符串是否匹配
第二步，状态初始化。初始化当匹配字符串为空时的匹配状态（即j=0时的状态），因为除了原字符串为空时，dp[0][0]=True，其余的情况下dp[x][0]=False，所以只需要初始化dp[0][0]=True即可
第三步，状态转移。当判断前i个字符和前j个匹配字符是否匹配时，这里先预先定义俩字符匹配为匹配字符为.或者匹配字符和原字符两者相等。
- 如果最后一个匹配字符为号，并且倒数第二个匹配字符和原字符串最后一个字符匹配，可以选择让匹配一次，去除当前s子串中匹配的部分，此时的状态转移为dp[i][j]=dp[i-1][j]，当选择让*匹配0个，则去除匹配子串中的x*组合，此时状态转移为dp[i][j]=dp[i][j-2]；
- 如果最后一个匹配字符为*，并且倒数第二个匹配字符和原字符串最后一个字符不匹配，则只能选择让*匹配0次，此时dp[i][j]=dp[i][j-2]；
- 如果最后一个匹配字符不为*号，并且该匹配字符与原字符串中最后一个字符匹配，此时的转移方程为dp[i][j]=dp[i-1][j-1]；
- 如果最后一个匹配字符不为*号，并且该匹配字符与原字符串最后一个字符不匹配，则当前的原字符串和匹配字符串一定无法匹配，即dp[i][j]=False。
经过遍历，最终的dp[sLen][pLen]即为题解
3.解题代码
Python代码
class Solution:
def isMatch(self, s: str, p: str) -> bool:
sLen,pLen=len(s),len(p)
# 第一步，状态定义；dp[i][j]为s的前i个字符串和p的前j个字符串是否匹配
dp=[[False]*(pLen+1) for i in range(sLen+1)]
# 第二步，状态初始化。初始化当匹配字符串为空时的匹配状态（即j=0时的状态），因为除了原字符串为空时，dp[0][0]=True，其余的情况下dp[x][0]=False，所以只需要初始化dp[0][0]=True即可
dp[0][0]=True # 两个都是空字符串时，匹配
# 第三步，状态转移。当判断前i个字符和前j个匹配字符是否匹配时，这里先预先定义俩字符匹配为匹配字符为.或者匹配字符和原字符两者相等。如果最后一个匹配字符为*号，并且倒数第二个匹配字符和原字符串最后一个字符匹配，可以选择让*匹配一次，去除当前s子串中匹配的部分，此时的状态转移为dp[i][j]=dp[i-1][j]，当选择让*匹配0个，则去除匹配子串中的x*组合，此时状态转移为dp[i][j]=dp[i][j-2]；如果最后一个匹配字符为*，并且倒数第二个匹配字符和原字符串最后一个字符不匹配，则只能选择让*匹配0次，此时dp[i][j]=dp[i][j-2]；如果最后一个匹配字符不为*号，并且该匹配字符与原字符串中最后一个字符匹配，此时的转移方程为dp[i][j]=dp[i-1][j-1]；如果最后一个匹配字符不为*号，并且该匹配字符与原字符串最后一个字符不匹配，则当前的原字符串和匹配字符串一定无法匹配，即dp[i][j]=False。经过遍历，最终的dp[sLen][pLen]即为题解
# > 判断s[i]字符和p的p[j]字符是否匹配
def match(i,j):
if i<0 or j<0:
return False
if p[j]==".":
return True
elif p[j]==s[i]:
return True
else:
return False
for i in range(sLen+1):
for j in range(1,pLen+1):
if p[j-1]!="*":
if match(i-1,j-1):
dp[i][j]=dp[i-1][j-1]
else:
dp[i][j]=False
else:
if match(i-1,j-2):
dp[i][j]=dp[i-1][j] or dp[i][j-2]
else:
dp[i][j]=dp[i][j-2]
# print(dp[sLen][pLen])
return dp[sLen][pLen]
C++代码
class Solution {
public:
bool match(int i,int j,string s,string p){
if(i<0 || j<0){
return false;
}
if(p[j]=='.'){
return true;
}else if(p[j]==s[i]){
return true;
}else{
return false;
}
}
bool isMatch(string s, string p) {
int sLen=s.size(),pLen=p.size();
vector<vector<bool>> dp(sLen+1,vector<bool>(pLen+1,false));
dp[0][0]=true;
for(int i=0;i<sLen+1;++i){
for(int j=1;j<pLen+1;++j){
if(p[j-1]!='*'){
if(match(i-1,j-1,s,p)){
dp[i][j]=dp[i-1][j-1];
}else{
dp[i][j]=false;
}
}else{
if(match(i-1,j-2,s,p)){
dp[i][j]=dp[i-1][j] || dp[i][j-2];
}else{
dp[i][j]=dp[i][j-2];
}
}
}
}
return dp[sLen][pLen];
}
};
4.执行结果
