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];
}
};