AcWing 30. 正则表达式匹配
原题链接
困难
作者:
北尘_0
,
2024-03-17 22:48:37
,
所有人可见
,
阅读 8
class Solution {
public:
bool isMatch(string s, string p)
{
int n=s.size(),m=p.size();
s=" "+s,p=" "+p;
vector<vector<bool>> dp(n+1,vector<bool>(m+1));
dp[0][0]=true;
for(int i=2;i<m+1;i+=2)
{
if(p[i]=='*') dp[0][i]=true;
else break;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(p[j]=='*')
{
dp[i][j]=dp[i][j-2];
if((p[j-1]=='.' || p[j-1]==s[i]) && !dp[i][j])
{
dp[i][j]=dp[i-1][j];
}
}
else
{
if((s[i]==p[j] || p[j]=='.') && dp[i-1][j-1]==true) dp[i][j]=true;
}
}
}
return dp[n][m];
}
};