a***e
发帖数: 413 | 1 这个题https://oj.leetcode.com/problems/regular-expression-matching/
意思是说
bool isMatch(const char *s, const char *p)
s是个普通string （literal string）而p是regular expression是吗？
我看wiki上说也可以两个regular expressions match。我开始自己写的时候考虑s和p
都有*，.的情况，但后来写不下去了。
http://en.wikipedia.org/wiki/Regular_expression
看到的这个答案没有考虑s有*，.的情况，但OJ444个tests都通过了。
我还是不懂这一段的逻辑
while(*p==*s||(*p=='.'&&*s!='\0'))
{
if (isMatch(s,p+2))
return true;
s++;
}
bool isMatch( const char *s, const char *p) {
if (*p=='\0')
return *s=='\0';
if (*(p+1)!='*'){
if (*p==*s||(*p=='.'&&*s!='\0'))
return isMatch(s+1,p+1);
else
return false;
}
else {
while(*p==*s||(*p=='.'&&*s!='\0'))
{
if (isMatch(s,p+2))
return true;
s++;
}
return isMatch(s,p+2);
}
} | a***e
发帖数: 413 | 2 还有类似的题
https://oj.leetcode.com/problems/wildcard-matching/
我写的这种TLE，请问怎么计算这种recursion的复杂度啊？
bool isMatch(const char *s, const char *p) {
if (*p=='\0')
return (*s=='\0');
if (*p!='*')
{
if (*s==*p&&*s!='\0'||*p=='?')
{
s++;
p++;
return isMatch(s,p);
}
else
return false;
}
else
{
while(*p=='*')
p++;
if (*p=='\0')
return true;
bool f = isMatch(s,p);
while(!f &&*s!='\0')
{
s++;
f = isMatch(s,p);
}
if (!f)
return false;
else
{
return isMatch(s++,p++);
}
} | a***e
发帖数: 413 | | t*******e
发帖数: 274 | | a***e
发帖数: 413 | | a***e
发帖数: 413 | |
|
