大模拟
c++
class Solution {
public:
int dp[1005][1005];
bool ans;
bool isMatch(string s, string p) {
return judge(s,p,0,0);
}
bool judge(string s,string p,int i,int j)
{
if(dp[i][j]==-1)
return false;
if(i>=s.length())
{
if(j>=p.length())
{
return true;
}
else{
if(j==p.length()-1&&p[j]=='*')
{
return judge(s,p,i,j+1);
}
if(j<=p.length()-2&&p[j+1]=='*')
{
return judge(s,p,i,j+2);
}
return false;
}
}
if(j>=p.length())
{
dp[i][j]=-1;
return false;
}
if(p[j]=='.')
{
ans = judge(s,p,i+1,j+1);
if(ans==true)
return true;
else
{
if(j<p.length()-1&&p[j+1]=='*')
{
ans = judge(s,p,i,j+2);
if(ans==true)
return true;
for(int k=i+1;k<=s.length();k++)
{
ans = judge(s,p,k,j+2);
if(ans==true)
return true;
}
}
dp[i][j]=-1;
return false;
}
}
else if(p[j]=='*')
{
ans = judge(s,p,i,j+1);
if(ans==true)
return true;
dp[i][j]=-1;
return false;
}
else{
if(j<p.length()-1&&p[j+1]=='*')
{
if(p[j]==s[i])
{
ans = judge(s,p,i,j+2);
if(ans==true)
return true;
for(int k=i+1;k<=s.length();k++)
{
if(p[j]==s[k-1])
{
ans = judge(s,p,k,j+2);
if(ans==true)
return true;
}
else
break;
}
dp[i][j]=-1;
return false;
}
else
{
ans = judge(s,p,i,j+2);
if(ans==true)
return true;
dp[i][j]=-1;
return false;
}
}
else
{
if(p[j]==s[i])
{
ans=judge(s,p,i+1,j+1);
if(ans==true)
return true;
dp[i][j]=-1;
return false;
}
else
{
dp[i][j]=-1;
return false;
}
}
}
}
};