Problem:
Regular Expression Matching
class Solution {
public:
int sl, pl;
bool isMatch(string s, string p) {
sl=s.length();
pl=p.length();
if(pl==0) return sl==0;
return allMatch(s, 0, p, 0);
}
bool allMatch(string s, int scur, string p, int pcur)
{
if(pcur==pl) return scur==sl;
if(pcur+1<pl && p[pcur+1]=='*')
{
if(allMatch(s, scur, p, pcur+2))
return true;
if(p[pcur]=='.' || p[pcur]==s[scur])
{
while(scur<sl && (p[pcur]=='.' || p[pcur]==s[scur]))
{
if(allMatch(s, scur+1, p, pcur+2))
return true;
scur++;
}
}
}
else if(p[pcur]=='.' || p[pcur]==s[scur])
return allMatch(s, scur+1, p, pcur+1);
return false;
}
};
No comments:
Post a Comment