Leetcode 10. 正则表达式匹配

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 Falseif p[j]==".":return Trueelif p[j]==s[i]:return Trueelse:return Falsefor 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]=Falseelse: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];}
};